Nach einem Skript von Philipp Moor (Kantonsschule Zimmerberg).
Lernziele
- Erklären, was ein Alphabet, ein Wort und eine Sprache ist
- Zu einem Automaten mit Endzuständen entscheiden, ob er ein Wort annimmt
- In einem Satz beschreiben, welche Sprache ein Automat erkennt
- Zu einer beschriebenen Sprache selber einen Automaten zeichnen
- Begründen, warum ein endlicher Automat nicht beliebig weit zählen kann
3.1 Zeichen, Wort und Sprache
Definition: Alphabet, Wort, SpracheBevor ein Automat etwas prüfen kann, muss klar sein, was er zu lesen bekommt.
- Ein Alphabet ist eine endliche Menge von Zeichen, zum Beispiel
aundboder0und1.- Ein Wort ist eine endliche Folge von Zeichen aus dem Alphabet. Die Anzahl der Zeichen heisst Länge des Wortes.
- Das leere Wort ist das Wort ohne Zeichen. Seine Länge ist null.
- Eine Sprache ist eine Menge von Wörtern über einem Alphabet.
Ein Wort muss nichts bedeuten.
abbaist ein Wort über dem Alphabet ausaundb, und mehr wird von ihm nicht verlangt.
BeispielWir nehmen das Alphabet aus
aundbund die Sprache aller Wörter, in denen eine gerade Anzahlavorkommt. Welche der Wörteraa,ab,ba,bb,ababgehören dazu? Und wie steht es mit dem leeren Wort?
Eine Sprache ist eine MengeDamit gelten für Sprachen alle Regeln aus der Mengenlehre. Eine Sprache kann leer sein, sie kann endlich viele Wörter enthalten, und sie kann unendlich viele enthalten. Die Sprache aus dem Beispiel ist unendlich: an jedes Wort darin lässt sich ein
banhängen, und man erhält wieder eines.
3.2 Der Automat sagt ja oder nein
Definition: Endzustände und erkannte SpracheSoll ein endlicher Automat Wörter prüfen, so bekommt er einen fünften Teil.
- die Endzustände: einige der Zustände werden als Endzustände ausgezeichnet und im Diagramm mit einem doppelten Kreis gezeichnet
Der Automat beginnt im Startzustand und liest das Wort Zeichen für Zeichen. Steht er nach dem letzten Zeichen in einem Endzustand, so nimmt er das Wort an, sonst weist er es ab.
Die Sprache, die der Automat erkennt, ist die Menge aller Wörter, die er annimmt.
BeispielDer folgende Automat liest Wörter über
aundb. Was macht er mitabba, was mitabb, und welche Sprache erkennt er?
Das ist derselbe Automat wie der Paritätsautomat aus Teil 1. Dort gab er nach jedem Zeichen g oder u aus, hier sagt er am Schluss nur noch ja oder nein.
Lernvideo
Auch dieses Video fasst die Teile zu einem Tupel zusammen und nennt die Zustände , , .
Verwandt: Suchmuster in PythonDie regulären Ausdrücke, mit denen Sie in Python nach Mustern in Texten suchen, beschreiben genau die Sprachen, die ein endlicher Automat erkennen kann. Die Suchfunktion baut im Hintergrund einen solchen Automaten und lässt ihn über den Text laufen.
3.3 Grenzen des endlichen Gedächtnisses
Ein endlicher Automat hat keinen Speicher ausser seinen Zuständen. Was er sich merken will, muss er in endlich viele Fälle einteilen. Für manche Sprachen reicht das grundsätzlich nicht.
Warum ein Automat nicht beliebig weit zählen kannKein endlicher Automat erkennt die Sprache aller Wörter, die aus einigen
aund danach gleich vielenbbestehen, alsoab,aabb,aaabbbund so weiter.
Dem Automaten fehlt ein Speicher, der beliebig gross werden darf. Genau den bekommt die Maschine in Teil 3: ein Band, auf dem sie lesen und schreiben kann, so lang wie nötig.
3.4 Aufgaben
Aufgabe 3.4.1Wir arbeiten mit dem Alphabet aus
aundb.(a) Schreiben Sie alle Wörter der Länge zwei auf. Wie viele sind es?
(b) Welche der Wörter
ab,ba,b,aabund das leere Wort gehören zur Sprache aller Wörter, die mitaanfangen?(c) Wie viele Wörter der Länge drei gibt es?
Aufgabe 3.4.2Zeichnen Sie einen Automaten über
aundb, der genau die Wörter annimmt, in denen mindestens einavorkommt. Zwei Zustände genügen.
Aufgabe 3.4.3Gegeben ist der folgende Automat über dem Alphabet aus
aundb.(a) Prüfen Sie für
ab,ba,abb,baaundb, ob der Automat sie annimmt.(b) Beschreiben Sie in einem Satz, welche Sprache er erkennt.
(c) Nimmt er das leere Wort an?
Aufgabe 3.4.4Zeichnen Sie einen Automaten über
aundb, der genau die Wörter annimmt, die mitabeginnen und mitbaufhören. Denken Sie auch an die Wörter, die schon mitbbeginnen.
Aufgabe 3.4.5Zeichnen Sie einen Automaten über
aundb, der genau die Wörter annimmt, in denen nie zweiaunmittelbar nacheinander stehen. Das leere Wort soll angenommen werden.
Aufgabe 3.4.6Zeichnen Sie einen Automaten über
0und1, der genau die Wörter annimmt, deren Länge durch drei teilbar ist. Auf die Zeichen selbst kommt es dabei nicht an.
Aufgabe 3.4.7Zeichnen Sie einen Automaten über
aundb, der genau die Wörter annimmt, in denen die Folgebbnicht vorkommt. Das leere Wort soll angenommen werden.
Aufgabe 3.4.8Zeichnen Sie einen Automaten über
aundb, der genau die Wörter annimmt, in denen die Folgeabnicht vorkommt. Überlegen Sie zuerst, wie solche Wörter aussehen.
Weitere Aufgaben
Zusatzaufgabe 3.4.9Zeichnen Sie einen Automaten über
aundb, der genau die Wörter annimmt, in denen irgendwo die Folgeabvorkommt.
Zusatzaufgabe 3.4.10Der folgende Automat nimmt genau die Wörter an, die auf
benden.Ändern Sie ihn so, dass er genau die Wörter annimmt, die nicht auf
benden. Ändern Sie so wenig wie möglich und beschreiben Sie die Regel, die dahintersteckt.