|
Die Eigenschaften der von Kellerautomaten akzeptierten und von kontextfreien Sprachen generierten Sprachen legen nah, dass sie für die gleiche Sprachklasse stehen. Die Äquivalenz der beiden Konzepte wird skizziert werden.
Gibt es für eine Sprache L eine kf. Grammatik, so muss auch ein Kellerautomat existieren, der L akzeptiert.
Somit sind bereits zwei Konzepte bekannt, von einer Sprache zu zeigen, dass sie mindestens kontextfrei ist. 1
Nach dem Satz von Chomsky-Schützenberger kann von einer Sprache gezeigt werden, dass sie kontextfrei ist. Das Verfahren wird vorgestellt.
___________
1 Eine Sprache, für die eine kf. Grammatik oder ein KA existiert, kann auch regulär sein. In so einem Fall ist die vorliegende Grammatik nicht die beschränkteste.
|
1
Äquivalenz von KA und kf. Grammatiken
