Zusammenhang zwischen Regel und Automatenübergang
|
Eine Ähnlichkeit zwischen diesen Systemen wird sofort durch die repräsentierbaren Sprachen deutlich.
In beiden Systemen werden Informationen zum Verlauf der bisherigen Analyse (respektive Ableitung)
durch einen Zustand (bzw. ein Nichtterminal) kodiert.
Somit können Abhängigkeiten nur durch die Einführung neuer Zustände (Nichtterminale) ausgedrückt werden.
Da jedoch sowohl Zustandsmenge als auch Alphabete "klein und endlich" bleiben sollen, ist es mit diesen Mechanismen nicht möglich,
sich unendliche Abhängigkeiten zu merken.
Die Umsetzung von einem System ins andere ist fast 1 zu 1.
Das Regelformat der rechtslinearen Grammatiken kann direkt in einen Automatenübergang umgesetzt werden:
Nichtterminal1 -> Terminal Nichtterminal2
führt zu
[Nichtterminal2]Zustand 
([Nichtterminal1]Zustand,Terminal).
Dieser Schritt wird durch die Darstellung mittels Graph besonders deutlich.
Der Zustandsmenge des Automaten entspricht das Nichtterminalphabet,
das Terminalalphabet bleibt unverändert, der Startzustand hat seine Entsprechung im Startsymbol der Grammatik.
Einer besonderen Behandlung bedarf die Umsetzung der Endzustände.
Das Verfahren zur Überführung eines Endlichen Automaten in eine Grammatik und der umgekehrte Fall
wird in Abschnitt 4.3.1 beschrieben.
|
Übersicht: Sprachklassen
