Einer der häufigsten Anwendungsfälle für einen Akzeptor ist eine Syntaxanalyse, dies kann sich konkret auf eine bestimmte Sprache beziehen oder nur auf einen speziellen Kontext.
Um beispielsweise ein in einer Programmiersprache geschriebenes Programm ausführen zu können, muss dieses in Maschinencode übersetzt werden. Dies geschieht u.a. durch einen Scanner und einen Parser.
Ein Scanner überprüft, ob Wörter richtig geschrieben sind, ersetzt diese mit Tokens – er vereinfacht quasi den zu testenden Text. Ein darauf folgender Parser überprüft die Syntax des Textes. Damit sind Scanner und Parser Automaten, insbesondere ein Transduktor und ein Akzeptor.
Praktisch sind Scanner und Parser komplexer aufgebaut – für unsere Betrachtungen an dieser Stelle genügt die Sichtweise auf die Automaten.
Beispiel (Lachautomat)
Untersuchen wir beispielhaft einen Akzeptor, der ein korrektes Lachen der Form „ha!“, „haha!“, „hahaha!“ … erkennen soll.
Die würde ein Akzeptor mit der folgenden Übergangsfunktion erkennen:
Der Übersichtlichkeit wegen, werden wir zukünftig alle Pfeile, die in einen Fehlerzustand führen im Übergangsgraphen nicht angeben, es werden also nur die korrekten Übergängen angegeben.
Die Definition des Automaten wäre dann die folgende:
A = (X,Z,\delta,z_0,Z_E) \\ X = \{a, h, !\} \\ Z = \{q_0,q_1,q_2,q_3\} \\ \delta (h,q_0) = q_1;\\ \delta (a,q_1) = q_2; \\ \delta (h,q_2) = q_1; \delta (!,q_2) = q_3 \\ z_0 = q_0 \\ Z_E = \{q_3\}
Der dargestellte Automat akzeptiert also alle Worte einer Sprache „Lachen“. Später werden wir eine solche Sprache auch durch eine Grammatik beschreiben (hier schon einmal ein Ausblick):
Alle Worte einer Sprache (also alle Worte, die durch den Akzeptor dargestellt werden) kann man auch durch einen regulären Ausdruck angeben …
ha(a|h)*!
… oder als Sprachmenge formulieren …
L(G) = \{ha(a|h)^{*}!\} oder L(G) = \{ (ha)^{n}\ !\ |\ n>0 \}
… oder auch mithilfe eines Syntaxdiagramms darstellen:
