Gegeben sei der NFA N = (Σ, Z, δ, {z0}, F) mit Σ = {0, 1}, Z = {z0, z1, z2, z3}, F = {z2} und δ wie folgt:
Konstruieren Sie einen zu N äquivalenten DFA M′. Dabei ist M′ in der formalen Darstellung anzugeben, nicht als Zustandsgraph und prüfen Sie schrittweise mit Hilfe der erweiterten Überführungsfunktion von N, ob w = 0101 ∈ L(N) gilt.
Überlegen Sie sich, ob Sie wirklich alle möglichen Zustände in der Potenzmenge betrachtenmüssen. Wenn Sie Ihre Zustände umbenennen wollen, müssen Sie dies angemessen definieren.
