1.5 Grenzen von EA
Endliche Automaten kennen jeweils nur ihren aktuellen Zustand und die nächste Eingabe. Sie können aber nicht beliebig weit zählen. Betrachten wir ein paar Beispiele um zu verstehen, was damit gemeint ist.
Beispiel \(0011\)
Wir möchten einen EA konstruieren, der nur für die Eingabefolge 0011 in einem akzeptierenden Zustand landet. Dieser EA kann also zwei Nullen und zwei Einsen abzählen.
Beispiel \(000111\)
Wir möchten einen EA konstruieren, der nur für die Eingabefolge 000111 in einem akzeptierenden Zustand landet. Dieser EA kann also drei Nullen und drei Einsen abzählen.
Beispiel \(\underbrace{00..0}_{n}\underbrace{11..1}_{n}\)
Nun möchten wir die letzten beiden Beispiele verallgemeinern. Wir möchten einen EA konstruieren, der nur für die Eingabefolge \(\underbrace{00..0}_{n}\underbrace{11..1}_{n}\) (also bestehend aus einer beliebigen Anzahl Nullen, gefolgt von derselben Anzahl Einsen) in einem akzeptierenden Zustand landet. Das \(n\) ist aber nicht fest. D.h. er soll beispielsweise 0011 aber auch 00001111 akzeptieren. Dieser EA kann also auf jede Zahl zählen, sich diese merken, erneut zählen und vergleichen, ob es dieselbe Anzahl ist. Dieser EA müsste folgendermassen aussehen.
Das Skizzierte ist jedoch kein EA, da er unendlich viele Zustände bräuchte. (EA dürfen per Definition nur endlich viele Zustände haben.)
HinweiseBeispiel \(\underbrace{00..0}_{n}\underbrace{11..1}_{m}\)
Im Gegensatz zum letzten Beispiel ist es möglich einen EA zu konstruieren, der nur Eingabefolgen akzeptiert, die aus beliebig vielen Nullen gefolgt von beliebig vielen Einsen bestehen. Der entscheidende Unterschied ist, dass es nicht gleichviele Nullen und Einsen sein müssen. So muss der EA nicht mitzählen und sich die Anzahl Nullen auch nicht merken. Der folgende \(ε\)-NEA erfüllt das hier Gewünschte.
Hier haben Sie die Option Ihre Notizen zu diesem Abschnitt hochzuladen. Wir empfehlen eine sinnvolle Beschriftung z.B. 1_5_GrenzenEA_Notizen.