Informatik Grundlagen – Endliche Automaten und Zustandsmaschinen
Karteikarten zum Thema „Informatik“ · 15 Karten · von atrio. Beispiele: Was ist ein deterministischer endlicher Automat (DFA)? · Was unterscheidet einen NFA …
Karten
15 KartenWas ist ein deterministischer endlicher Automat (DFA)?
Rückseite
Ein DFA ist ein 5-Tupel (Z, Σ, δ, z₀, F) mit eindeutiger Übergangsfunktion δ: Z × Σ → Z für jedes Symbol.
Was unterscheidet einen NFA von einem DFA?
Rückseite
Beim NFA erlaubt die Übergangsfunktion δ: Z × Σ → 𝒫(Z) mehrere oder keine Folgezustände pro Symbol; ε-Übergänge sind möglich.
Wozu dienen ε-Übergänge in einem NFA?
Rückseite
ε-Übergänge ermöglichen Zustandswechsel ohne Eingabesymbol-Verbrauch; sie vereinfachen die Konstruktion aus regulären Ausdrücken (Thompson).
Wie funktioniert die Potenzmengenkonstruktion (NFA → DFA)?
Rückseite
Jeder DFA-Zustand entspricht einer Menge von NFA-Zuständen; Startzustand ist ε-Hülle von {z₀}; Übergänge bilden ε-Hüllen der vereinigten NFA-Nachfolger.
Was besagt das Pumping-Lemma für reguläre Sprachen?
Rückseite
Für reguläre L gibt es n≥1: Jedes w∈L mit |w|≥n lässt sich als w=xyz mit |xy|≤n, |y|≥1 und xyⁱz∈L (∀i≥0) zerlegen.
Wann sind zwei Zustände eines DFA äquivalent (Myhill-Nerode)?
Rückseite
Zwei Zustände sind äquivalent, wenn für alle Fortsetzungen entweder beide in Endzuständen landen oder beide nicht – sie sind für die Sprache ununterscheidbar.
Was ist ein Moore-Automat?
Rückseite
Ein Moore-Automat ist ein 6-Tupel (Z, Σ, Δ, δ, λ, z₀) mit Ausgabe-Funktion λ: Z → Δ; Ausgabe hängt nur vom aktuellen Zustand ab.
Was ist ein Mealy-Automat?
Rückseite
Ein Mealy-Automat hat Ausgabe-Funktion λ: Z × Σ → Δ; Ausgabe hängt vom aktuellen Zustand und dem eingelesenen Symbol ab.
Welche Abgeschlossenheitseigenschaften besitzen reguläre Sprachen?
Rückseite
Reguläre Sprachen sind abgeschlossen unter Vereinigung, Durchschnitt, Komplement, Differenz, Verkettung, Stern und Homomorphismen.
Wie wandelt man einen regulären Ausdruck in einen NFA um?
Rückseite
Die Thompson-Konstruktion baut rekursiv NFAs für Basisfälle (∅, ε, a) und Operatoren (Union, Verkettung, Stern) mit ε-Übergängen zusammen.
Was besagt das Lemma von Arden?
Rückseite
Für Sprachen-Gleichung X = A·X ∪ B mit ε ∉ A lautet die eindeutige Lösung X = A*·B.
Wie erkennt man mit dem Pumping-Lemma Nicht-Regularität?
Rückseite
Wähle w∈L mit |w|≥n; zeige, dass für jede gültige Zerlegung w=xyz ein i≥0 existiert mit xyⁱz∉L – dann ist L nicht regulär.
Was ist der Unterschied zwischen DFA-Minimierung und NFA-Minimierung?
Rückseite
DFA-Minimierung ist effizient lösbar (Hopcroft-Algorithmus O(n log n)); NFA-Minimierung ist PSPACE-vollständig und damit algorithmisch schwer.
Welche Rolle spielen endliche Automaten im Compilerbau?
Rückseite
Im Lexer (Scanner) erkennen deterministische endliche Automaten Tokens wie Schlüsselwörter, Bezeichner und Operatoren anhand regulärer Ausdrücke.
Was definiert eine reguläre Sprache formal?
Rückseite
Eine Sprache ist regulär, genau wenn sie von einem endlichen Automaten (DFA oder NFA) akzeptiert wird oder durch einen regulären Ausdruck beschrieben wird.