Automaten werden z. B. als Grundlage für Compiler verwendet. Ein Compiler soll erkennen, ob die Syntax der in den Computer eingegebenen Codes richtig ist. Der zugrundeliegende Automat muss also gewährleisten, dass nur Codebausteine, die programmiersprachenkonform sind, akzeptiert werden. Ein solcher Automat muss somit eine vorgegebene „Sprache“ akzeptieren.

Nach diesem Kapitel kannst du …

• endliche Automaten als Graphen darstellen.
• natürliche und formale Sprachen unterscheiden und außerdem Begriffe einer formalen Sprache wie z. B. Sprache des Automaten oder Wort verwenden.
• Sprachen von Automaten beschreiben.
• zu einer gegebenen Sprache einen Automaten konstruieren.

Du hast bis jetzt viele verschiedene Automaten kennengelernt. Außerdem hast du im letzten Kapitel gelernt, wie man Automaten verändert und damit auch das Akzeptanzverhalten des Automaten beeinflusst. Auf diesem Wissen baust du nun auf, denn jetzt konstruierst du deinen Automaten von Grund auf selber! Lies dazu zunächst noch ein Beispiel durch:

Es soll ein Automat konstruiert werden, der eine vierstellige Zahl übergeben bekommt. Der Automat soll diese Zahl akzeptieren, wenn sie gerade ist und sie verwerfen, wenn sie ungerade ist. Man kann diesem Automaten außerdem ausschließlich vierstellige Zahlen übergeben; so muss zum Beispiel für die Zahl 100 die vierstellige Zahl 0100 eingegeben werden. Die vorderen Nullen haben dabei keinerlei Bedeutung.

Wie muss aber ein Automat aussehen, der nur gerade Zahlen akzeptiert? Natürlich ist bei dieser Frage nur die letzte Ziffer der Zahl interessant, denn schon an dieser kann man ablesen, ob eine Zahl gerade ist, oder nicht. Die ersten drei Ziffern der Zahl sind also für den Automaten uninteressant. Das lässt sich folgendermaßen darstellen:

Dieser Automat „zählt“ praktisch nur die ersten drei Ziffern drei und ignoriert alle anderen Eigenschaften der Eingaben. Nur die letzte, die vierte Ziffer, ist von Bedeutung für unser Beispiel. Denn wenn diese Ziffer gleich 0, 2, 4, 6, oder 8 ist, ist die Zahl gerade. Unser Automat soll in diesem Fall die Zahl somit akzeptieren.