Typische Fehler

So wird es oft gemacht: Ein DEA für Dezimalzahlen steht nach 3,5 im Endzustand — „also wird 3,5, akzeptiert“.

Warum falsch: Entscheidend ist nur der Zustand nach dem letzten Zeichen. Das zweite Komma führt in den Fehlerzustand.

Richtig ist: Zustandsfolge bis zum Ende verfolgen: … → zF → abgelehnt.

Erst nach dem letzten Zeichen wird entschieden.

So wird es oft gemacht: Im Graphen fehlen Pfeile, ein Hinweis auf zF steht nirgends.

Warum falsch: Ein DEA ist vollständig anzugeben. Fehlende Pfeile sind nur erlaubt, wenn ausdrücklich auf den Fehlerzustand hingewiesen wird.

Richtig ist: Satz ergänzen: „Nicht eingezeichnete Übergänge führen in den Fehlerzustand zF.“

Weglassen nur mit Vermerk.

So wird es oft gemacht: Ein Übergang ohne Ausgabe wird mit „a / 0“ beschriftet oder die Ausgabe fehlt ganz.

Warum falsch: 0 ist ein Zeichen aus \(\Omega\) — es würde tatsächlich ausgegeben. Fehlt der Schrägstrich, ist der Übergang unvollständig.

Richtig ist: Keine Ausgabe wird als \(\varepsilon\) notiert: „a / ε“.

Nichts ausgeben heißt ε.

So wird es oft gemacht: „Ein DEA mit 1000 Zuständen erkennt \(\{a^nb^n\}\) — längere Wörter kommen nicht vor.“

Warum falsch: Bei \(a^{1000}\) wiederholt sich ein Zustand; dann werden \(a^ib^i\) und \(a^jb^i\) gleich beurteilt. Das gilt für jede Zustandszahl.

Richtig ist: Kein DEA erkennt \(\{a^nb^n\}\); für \(n\le 1000\) ist es eine andere, endliche Sprache.

Unbeschränkt zählen kann kein DEA.

So wird es oft gemacht: Nach (#,a):A# wird notiert: „oben liegt #, darunter A“.

Warum falsch: Die abgelegten Zeichen werden von rechts nach links auf den Keller gelegt: erst #, dann A.

Richtig ist: Nach (#,a):A# liegt A oben; der Keller wird oben links notiert: A#.

Links in W = danach oben.

So wird es oft gemacht: Ein Automat für \(\{a^nb^n\}\) hat einen Endzustand, der mit (A,b):ε erreicht wird.

Warum falsch: Dann ist schon nach dem ersten b Schluss — aab würde akzeptiert, obwohl noch ein A im Keller liegt.

Richtig ist: Erst wenn # wieder oben liegt, führt (#,ε):# in den Endzustand.

Fertig ist es erst, wenn # oben liegt.

So wird es oft gemacht: Von z1 gehen (A,ε):A und (A,b):ε aus — „der Automat ist trotzdem deterministisch“.

Warum falsch: Mit A oben könnte er den ε-Übergang oder den b-Übergang nehmen. Die Anlage verbietet das für deterministische Kellerautomaten.

Richtig ist: Ein ε-Übergang darf nur ein oberstes Kellerzeichen verwenden, zu dem es sonst keinen Übergang gibt, z. B. (#,ε):#.

ε-Übergang nur ohne Konkurrenz.

So wird es oft gemacht: Eine Ableitung wird als „S → aA → abB → ab“ notiert.

Warum falsch: Der einfache Pfeil gehört zu Regeln, der Doppelpfeil verbindet Satzformen.

Richtig ist: S ⇒ aA ⇒ abB ⇒ ab; Regeln bleiben S → aA, A → bB, B → ε.

Regel mit →, Ableitung mit ⇒.

So wird es oft gemacht: Eine „reguläre“ Grammatik enthält S → aS | Sb.

Warum falsch: S → Sb wächst links; gemischt mit S → aS entsteht keine reguläre Grammatik mehr.

Richtig ist: Nur Regeln A → aB, A → a, A → ε — das Nichtterminal steht immer rechts.

Regulär heißt: Nichtterminal ganz rechts.

So wird es oft gemacht: Bei der Umwandlung Grammatik → DEA wird aus A → a eine Schleife a an A, und A wird Endzustand.

Warum falsch: Dann akzeptiert der DEA auch Wörter, die nach diesem a weitergehen, obwohl die Ableitung dort endet.

Richtig ist: Pfeil A –a→ zE in einen neuen Endzustand zE ohne ausgehende Pfeile.

A → a braucht einen eigenen Endzustand.

So wird es oft gemacht: Für „mindestens zwei a“ bekommt das Nichtterminal „genau ein a erzeugt“ die Regel A → ε.

Warum falsch: Die ε-Regel erlaubt das Ende der Ableitung genau dort — hier entstünde z. B. ab.

Richtig ist: ε-Regel nur bei Nichtterminalen, deren Bedeutung die Bedingung erfüllt (hier „mindestens zwei a“).

ε-Regel = Endzustand: genau dort, wo das Wort fertig sein darf.

So wird es oft gemacht: „S → aSa | bSb | ε ist nicht regulär, also ist die Sprache nicht regulär.“

Warum falsch: Eine einzelne Grammatik beweist nichts: Es könnte eine andere, reguläre Grammatik für dieselbe Sprache geben.

Richtig ist: Nicht regulär zeigt man mit dem Schubfach-Argument über alle DEA.

Sprache ≠ Grammatik — Beweis über alle Automaten.