Endliche Automaten und rechtslineare Grammatiken

Die Menge aller Sprachen, die ein endlicher Automat erkennen kann, ist die gleiche wie die Menge aller Sprachen, die durch eine rechtslineare Grammatik erzeugt werden können.

Deshalb gibt es zu jeder rechtslinearen Grammatik einen endlichen Automaten, so dass die von der rechtslinearen Grammatik erzeugte Sprache von dem endlichen Automaten erkannt werden kann.

Endliche Automaten und rechtslineare Grammatiken

Wir betrachten rechtlineare Grammatiken G und endliche Automaten EA. Es fällt einem auf, dass:

-       die Menge der Nonterminalsymbole aus G der Zustandsmenge des EA ähnelt

-       die Terminalsymbole aus G dem Eingabealphabet des EA ähneln

-       die Nonterminalsymbole, von denen aus mit Regeln der rechtslinearen Grammatik G eine Ableitung des leeren Wortes ermöglicht werden, den Endzuständen des EA ähneln.

Man hat einen Algorithmus entwickelt, der aus einem endlichen deterministischen Automaten eine rechtslineare Grammatik erzeugt, und auch einen Algorithmus entwickelt, der aus einer rechtslinearen Grammatik einen nichtdeterministischen endlichen Automaten konstruiert. In beiden Fällen gilt, dass die von der rechtslinearen Grammatik erzeugte Sprache von dem endlichen Automaten akzeptiert wird.

Man kann daraus nun folgern, wenn man ausschließlich immer dasselbe Eingabealphabet E betrachtet, dass rechtslineare Sprachen von sowohl deterministischen als auch nichtdeterministischen endlichen Automaten erkannt werden, und dass Sie außerdem auch noch identisch zu den regulären Sprachen und den regulären Ausdrücken sind.