Hi alle zusammen,
wir sitzen schon etwas länger in der Uni und haben schon einige Tafeln hier vollgeschrieben zum Skript zu "Formale Sprachen".
Auf Seite 35, deutsche Skript, steht ein Korollar und zwar
(i) Jede kontextfreie Sprache kann von einem Kellerautomaten mit nur einen Zustand akzeptiert werden.
Nehmen wir jetzt dazu die bekannte a^n b^n
Diese Sprache ist auch auf der
Wikipedia-Seite als Beispiel angegeben.
Das Beispiel kann man bei Wiki auf 2 Zustände zurückführen, indem man den z2 einfach durch z1 ersetzt am Ende.
Hat aber jemand eine Lösung, wie man den Automaten auf 1 Zustand zurückführen kann, so wie es im Korollar steht?
Danke und Grüße
Lars