Fachrat Informatik - Forum

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

Quoted

(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

Okey, wir haben einen nicht-deterministischen nach mehreren Stunden gefunden.

ohjeeee!!!


Bei Interesse, poste ich den.

Stahlbausaal