Satz Äquivalenz kontextfreie Grammatik und Kellerautomat
Einfache Sprache
Def. Satz Äquivalenz kontextfreie Grammatik und Kellerautomat
Die Klasse der Kontextfreien Sprachen ist gleich der Klasse der durch Kellerautomaten erkannten Sprachen.
Dabei ist nach dem Satz durch Endzustand und durch leeren Keller erkannt ist äquivalent egal, ob der Kellerautomat durch Endzustand oder leeren Keller akzeptiert.
Beweisidee: Wir zeigen wie man eine beliebige Kontextfreie Sprache, repräsentiert durch eine Kontextfreie Grammatik, in einen NDKA, der durch leeren Keller akzeptiert, umwandelt wobei beide die gleiche Sprache erkennen.
Beweis:
Home: