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, Sprache

Bevor ein Automat etwas prüfen kann, muss klar sein, was er zu lesen bekommt.

  • Ein Alphabet ist eine endliche Menge von Zeichen, zum Beispiel a und b oder 0 und 1.
  • 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. abba ist ein Wort über dem Alphabet aus a und b, und mehr wird von ihm nicht verlangt.

Beispiel

Wir nehmen das Alphabet aus a und b und die Sprache aller Wörter, in denen eine gerade Anzahl a vorkommt. Welche der Wörter aa, ab, ba, bb, abab gehören dazu? Und wie steht es mit dem leeren Wort?

Eine Sprache ist eine Menge

Damit 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 b anhängen, und man erhält wieder eines.

3.2 Der Automat sagt ja oder nein

Definition: Endzustände und erkannte Sprache

Soll ein endlicher Automat Wörter prüfen, so bekommt er einen fünften Teil.

  1. 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.

Beispiel

Der folgende Automat liest Wörter über a und b. Was macht er mit abba, was mit abb, und welche Sprache erkennt er?

Zustandsdiagramm mit zwei Zuständen g und u über a und bZustandsdiagramm mit zwei Zuständen g und u über a und b

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 z0z_0, z1z_1, z2z_2.

Verwandt: Suchmuster in Python

Die 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 kann

Kein endlicher Automat erkennt die Sprache aller Wörter, die aus einigen a und danach gleich vielen b bestehen, also ab, aabb, aaabbb und 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.1

Wir arbeiten mit dem Alphabet aus a und b.

(a) Schreiben Sie alle Wörter der Länge zwei auf. Wie viele sind es?

(b) Welche der Wörter ab, ba, b, aab und das leere Wort gehören zur Sprache aller Wörter, die mit a anfangen?

(c) Wie viele Wörter der Länge drei gibt es?

Aufgabe 3.4.2

Zeichnen Sie einen Automaten über a und b, der genau die Wörter annimmt, in denen mindestens ein a vorkommt. Zwei Zustände genügen.

Aufgabe 3.4.3

Gegeben ist der folgende Automat über dem Alphabet aus a und b.

Automat zu Aufgabe 3.4.3Automat zu Aufgabe 3.4.3

(a) Prüfen Sie für ab, ba, abb, baa und b, 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.4

Zeichnen Sie einen Automaten über a und b, der genau die Wörter annimmt, die mit a beginnen und mit b aufhören. Denken Sie auch an die Wörter, die schon mit b beginnen.

Aufgabe 3.4.5

Zeichnen Sie einen Automaten über a und b, der genau die Wörter annimmt, in denen nie zwei a unmittelbar nacheinander stehen. Das leere Wort soll angenommen werden.

Aufgabe 3.4.6

Zeichnen Sie einen Automaten über 0 und 1, 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.7

Zeichnen Sie einen Automaten über a und b, der genau die Wörter annimmt, in denen die Folge bb nicht vorkommt. Das leere Wort soll angenommen werden.

Aufgabe 3.4.8

Zeichnen Sie einen Automaten über a und b, der genau die Wörter annimmt, in denen die Folge ab nicht vorkommt. Überlegen Sie zuerst, wie solche Wörter aussehen.

Weitere Aufgaben

Zusatzaufgabe 3.4.9

Zeichnen Sie einen Automaten über a und b, der genau die Wörter annimmt, in denen irgendwo die Folge ab vorkommt.

Zusatzaufgabe 3.4.10

Der folgende Automat nimmt genau die Wörter an, die auf b enden.

Automat zu Zusatzaufgabe 3.4.10Automat zu Zusatzaufgabe 3.4.10

Ändern Sie ihn so, dass er genau die Wörter annimmt, die nicht auf b enden. Ändern Sie so wenig wie möglich und beschreiben Sie die Regel, die dahintersteckt.