Gymnasium OttweilerSkript zum Informatik-Grundkurs
Automaten und SprachenKapitel 5

Kapitel 5

Automaten und formale Sprachen

Skript Informatik · Grundkurs

Notebooks in diesem Kapitel NB05

Alle Notebooks der Klasse · Das grüne Schild an einer Überschrift zeigt, zu welchem Notebook der Abschnitt gehört.

PDF zum Ausdrucken zusammenstellen

Kreuze an, welche Abschnitte du brauchst. Die PDF hat dasselbe Aussehen wie das gedruckte Skript, mit Platz zum Schreiben. Jeden Abschnitt gibt es auch einzeln unter seiner Überschrift, das ganze Kapitel unten auf der Seite.

Sie geben im Onlineshop Ihre E-Mail-Adresse ein und vergessen das @. Noch bevor Sie auf „Bestellen“ klicken, färbt sich das Feld rot. Ob es die Adresse gibt, weiß die Seite nicht — aber dass max.mustermann.de keine sein kann, sieht sie sofort. So etwas passiert ständig um Sie herum: Das Drehkreuz im Freibad lässt Sie erst nach dem Chip durch, die Ampel weiß, dass nach Rot-Gelb Grün kommt, und Ihr Handy entsperrt sich erst nach der richtigen Ziffernfolge. Hinter all dem steckt dieselbe einfache Maschine. Um sie geht es in diesem Kapitel.

Auch ein Compiler liest Ihr Programm und weiß nach dem Bruchteil einer Sekunde, ob es regelgerecht aufgebaut ist. Er versteht dabei nicht, was Sie vorhaben — er prüft nur, ob die Zeichenfolge den Regeln der Sprache gehorcht. Genau diese Trennung macht ihn möglich: Form lässt sich mechanisch prüfen, Bedeutung nicht.

Dieses Kapitel baut das Werkzeug dafür auf. Erst die Frage, was eine Sprache formal überhaupt ist, dann Grammatiken als Regelwerk zum Erzeugen von Wörtern, dann endliche Automaten als Maschinen zum Erkennen von Wörtern. Am Ende steht ein Programm, das eine solche Maschine ausführt — und die Einsicht, wo diese einfachen Maschinen an ihre Grenze stoßen.

Lernziele

Am Ende dieses Kapitels können Sie

5.1Sprachen und ihre Regeln

Diesen Abschnitt als PDF (S. 2)

Tippen Sie in Ihren Taschenrechner 3 + × 4. Viele Modelle antworten mit Syntax ERROR: Die Zeichenfolge ist gar keine Rechnung, der Rechner kann sie nicht einmal lesen. Tippen Sie dagegen 5 ÷ 0, kommt Math ERROR: Die Eingabe ist tadellos gebaut, nur ergibt sie keinen Sinn. Ihr Taschenrechner unterscheidet damit genau die zwei Ebenen, um die es in diesem Abschnitt geht.

Sprachen dienen der Verständigung. Man unterscheidet natürliche Sprachen, die zwischen Menschen gewachsen sind (Deutsch, Französisch), und künstliche Sprachen, die jemand bewusst festgelegt hat. Programmiersprachen gehören dazu, aber auch die Formelsprache der Mathematik.

Jede Sprache gehorcht Regeln auf zwei Ebenen:

Der Unterschied lässt sich am Beispiel zeigen. Der Satz „Der Hund ist ein Insekt” ist syntaktisch einwandfrei und semantisch falsch. Die Zeile x := "drei" + 5; ist umgekehrt semantisch klar gemeint und syntaktisch bzw. typmäßig unzulässig. Ein Compiler prüft die Syntax vollständig, die Semantik nur zu einem kleinen Teil — deshalb erzeugt ein fehlerfrei übersetztes Programm noch lange nicht das gewünschte Ergebnis.

Dass natürliche Sprachen erheblich komplizierter sind als Programmiersprachen, zeigt schon ein einziger Satz:

Die deutsche Umgangssprache ist, wie jeder, der sie — und das wird an diesem Satz hier, den ich der Erläuterung wegen einschiebe, deutlich — lernen muss, weiß, eine sehr komplizierte Sprache.

Ein Mensch versteht ihn nach zweimaligem Lesen. Eine Maschine bräuchte dafür eine Grammatik, die beliebig tief verschachtelte Einschübe erlaubt — genau die Art von Struktur, an der die Automaten dieses Kapitels scheitern werden (Abschnitt 5.10).

Arbeitsauftrag 1
  1. Nennen Sie je zwei natürliche und zwei künstliche Sprachen und begründen Sie die Zuordnung.
  2. Geben Sie ein Beispiel für einen deutschen Satz, der syntaktisch korrekt, aber semantisch sinnlos ist — und eines für den umgekehrten Fall.
  3. Ihr Programm übersetzt fehlerfrei, liefert aber falsche Ergebnisse. Welche Ebene ist betroffen? Begründen Sie.
Lösung vergleichen
  1. Natürlich: Deutsch, Französisch — gewachsen im Gebrauch zwischen Menschen, ohne dass jemand die Regeln vorab festgelegt hat. Künstlich: Python, die Formelsprache der Mathematik — bewusst festgelegt, mit genau definierter Syntax.
  2. Syntaktisch korrekt, semantisch sinnlos: „Der Kühlschrank liest grüne Gedanken.“ Umgekehrt, gemeint ist etwas Klares, die Form ist falsch: „Ich morgen Kino gehen.“
  3. Die Semantik. Der Compiler hat die Syntax vollständig geprüft — sonst hätte er nicht übersetzt. Falsche Ergebnisse entstehen, weil das Programm etwas anderes bedeutet, als beabsichtigt war, etwa durch eine falsche Formel oder Bedingung.

5.2Vom Quelltext zur Maschine

Diesen Abschnitt als PDF (S. 3)

Bei einer Pressekonferenz überträgt eine Dolmetscherin jeden Satz, während der Gast noch spricht — wiederholt er sich, übersetzt sie eben noch einmal. Ein Roman dagegen wird einmal vollständig übersetzt, gedruckt und dann tausendfach gelesen, ohne dass der Übersetzer noch dabei ist. Genau diese beiden Wege gibt es auch, um ein Programm auf den Prozessor zu bringen.

Ein Prozessor versteht nur seine eigene Maschinensprache. Der Weg dorthin führt über eines von zwei Verfahren.

Ein Interpreter bekommt Programm und Eingabedaten gleichzeitig und führt jede Anweisung sofort aus. Jede Zeile ist ihm auch beim hundertsten Schleifendurchlauf wieder neu — das kostet Zeit, erlaubt aber sofortiges Ausprobieren. Python arbeitet im Kern so.

Ein Compiler (von to compile, zusammenstellen) trennt beides zeitlich: Zuerst wird das Programm unabhängig von allen Eingabedaten analysiert und in die Zielsprache übersetzt, danach läuft das Ergebnis beliebig oft. Delphi und C++ arbeiten so.

Quellsprache          →   Compiler   →   Zielsprache
(Pascal, Delphi, C)                      (Maschinen-, Assemblersprache)

Die Übersetzung zerfällt in zwei Phasen:

Merke

Der Lexer benutzt endliche Automaten (Abschnitt 5.6), der Parser eine Grammatik (Abschnitt 5.4). Dieses Kapitel baut also genau die beiden Werkzeuge, mit denen jeder Compiler beginnt.

Arbeitsauftrag 2
  1. Nennen Sie je einen Vorteil und einen Nachteil von Interpreter und Compiler.
  2. Zerlegen Sie die Zeile zaehler := zaehler + 1; von Hand in Token und benennen Sie deren Art.
  3. Warum meldet der Compiler einen Tippfehler in einem Schlüsselwort, nicht aber eine verwechselte Variable?
Lösung vergleichen
  1. Interpreter — Vorteil: Änderungen lassen sich sofort ausprobieren, ohne Übersetzungslauf. Nachteil: langsamer, weil jede Anweisung bei jeder Ausführung neu analysiert wird. Compiler — Vorteil: Das übersetzte Programm läuft schnell und beliebig oft. Nachteil: Nach jeder Änderung muss neu übersetzt werden.

  2. Sechs Token:

    Token Art
    zaehler Bezeichner
    := Zuweisungsoperator
    zaehler Bezeichner
    + arithmetischer Operator
    1 Zahl (Literal)
    ; Trennzeichen
  3. Ein vertipptes Schlüsselwort (whlie statt while) ist für den Lexer nur ein Bezeichner — an dieser Stelle verlangt die Grammatik aber ein Schlüsselwort, die syntaktische Analyse schlägt fehl. Eine verwechselte Variable ist dagegen ein gültiger Bezeichner an einer Stelle, an der ein Bezeichner stehen darf: Die Syntax stimmt, nur die Bedeutung nicht.

5.3Alphabet, Wort und Sprache

Diesen Abschnitt als PDF (S. 4)

Ihre Handy-PIN besteht aus vier Ziffern, und 0000 zählt genauso wie 4711. Erlaubt sind die zehn Zeichen 0 bis 9, jede PIN ist eine Folge aus genau vier davon. In der Sprache dieses Abschnitts: Das Ziffernfeld ist das Alphabet, jede PIN ein Wort der Länge 4, und die PINs, die Ihr Handy entsperren, bilden eine sehr kleine Sprache. Wie viele PINs es gibt, rechnen Sie mit dem Satz weiter unten in einer Zeile aus.

Definition (Alphabet). Ein Alphabet AA ist eine endliche, geordnete Menge von Zeichen.

Beispiele: A={0,1}A = \{0, 1\} für Dualzahlen, A={a,…,z,0,…,9}A = \{a, \dots, z, 0, \dots, 9\} für Bezeichner, für Pascal die Menge aller erlaubten Zeichen samt Schlüsselwörtern.

Definition (Wort). Ein Wort über AA ist eine endliche Folge von Zeichen aus AA. Das leere Wort wird mit ε\varepsilon bezeichnet und hat die Länge 0.

Für A={a,b,c}A = \{a, b, c\} sind aa, abab, cbacba, aaaaaaaa und ε\varepsilon Wörter.

Bezeichnung. Die Menge aller endlich langen Wörter über AA heißt A*A^*, die Menge aller Wörter der Länge nn heißt AnA^n.

A0={ε}A1={a,b,c}A2={aa,ab,ac,ba,bb,bc,ca,cb,cc}A^0 = \{\varepsilon\} \qquad A^1 = \{a, b, c\} \qquad A^2 = \{aa, ab, ac, ba, bb, bc, ca, cb, cc\}

Satz. Ist AA ein Alphabet mit kk Zeichen, so hat AnA^n genau knk^n Elemente. A*A^* hat unendlich viele Elemente — aber abzählbar unendlich viele, denn man kann die Wörter der Länge nach und innerhalb gleicher Länge alphabetisch aufzählen.

Definition (formale Sprache). Jede Teilmenge L⊆A*L \subseteq A^* heißt formale Sprache über AA.

Diese Definition ist großzügig: Jede beliebige Auswahl von Wörtern ist eine Sprache. Interessant werden nur die Sprachen, die sich endlich beschreiben lassen — durch eine Regel, eine Grammatik oder einen Automaten.

Arbeitsauftrag 3
  1. A={0,1}A = \{0, 1\}. Geben Sie A2A^2 und A3A^3 vollständig an. Wie viele Elemente hat A8A^8?
  2. A={x,y,z}A = \{x, y, z\}. Notieren Sie A1A^1 und die ersten zehn Wörter von A3A^3.
  3. A={a,b,c}A = \{a, b, c\}. Welche der folgenden Mengen sind formale Sprachen über AA? L4={}L_4 = \{\}, L5={ε}L_5 = \{\varepsilon\}, L6={x}L_6 = \{x\}, L7={a}L_7 = \{a\}. Begründen Sie.
  4. Beschreiben Sie in Worten: L10={b,ab,aab,aaab,…}L_{10} = \{b, ab, aab, aaab, \dots\} und L11={b,ba,baa,baaa,…}L_{11} = \{b, ba, baa, baaa, \dots\}.
  5. A={a,b,c}A = \{a, b, c\}. Geben Sie die Sprache aller Wörter der Länge 3 an, deren mittleres Zeichen ein cc ist. Wie viele Wörter sind das?
Lösung vergleichen
  1. A2={00,01,10,11}A^2 = \{00, 01, 10, 11\}, A3={000,001,010,011,100,101,110,111}A^3 = \{000, 001, 010, 011, 100, 101, 110, 111\}. A8A^8 hat 28=2562^8 = 256 Elemente.
  2. A1={x,y,z}A^1 = \{x, y, z\}. Die ersten zehn Wörter von A3A^3 in alphabetischer Reihenfolge: xxx,xxy,xxz,xyx,xyy,xyz,xzx,xzy,xzz,yxxxxx, xxy, xxz, xyx, xyy, xyz, xzx, xzy, xzz, yxx (von insgesamt 33=273^3 = 27).
  3. L4={}L_4 = \{\} ist eine formale Sprache — die leere Menge ist Teilmenge jeder Menge. L5={ε}L_5 = \{\varepsilon\} ebenfalls, denn ε∈A*\varepsilon \in A^*. L6={x}L_6 = \{x\} nicht: xx ist kein Zeichen aus AA, also kein Wort über AA. L7={a}L_7 = \{a\} ist eine formale Sprache. Beachten Sie: L4L_4 und L5L_5 sind verschieden — die eine enthält kein Wort, die andere genau eines, das leere.
  4. L10L_{10}: beliebig viele aa (auch keines), danach genau ein bb. L11L_{11}: genau ein bb, danach beliebig viele aa (auch keines).
  5. L={aca,acb,acc,bca,bcb,bcc,cca,ccb,ccc}L = \{aca, acb, acc, bca, bcb, bcc, cca, ccb, ccc\} — das sind 3⋅1⋅3=93 \cdot 1 \cdot 3 = 9 Wörter.

5.4Grammatiken

Diesen Abschnitt als PDF (S. 5–6)

Wählen Sie aus jeder Spalte ein Teil: Mein Hund | Mein kleiner Bruder | Der Drucker — hat — meine Hausaufgaben | mein Referat — gefressen | gelöscht | versteckt. Das ergibt 3⋅2⋅3=183 \cdot 2 \cdot 3 = 18 Ausreden, ohne dass Sie eine einzige auswendig lernen. So arbeitet eine Grammatik: wenige Regeln, viele Sätze. Ob die Ausrede glaubwürdig ist, entscheidet sie nicht — das ist Semantik.

Nicht jede Folge von Wörtern ergibt einen Satz:

Die erste und die dritte Zeile verstoßen gegen die Form, die zweite nur gegen den Inhalt. Für die Form zuständig ist die Grammatik. Sie hat zwei Aufgaben: die zulässigen Zeichenfolgen zu beschreiben und die Regeln dafür darzustellen. Die Semantik spielt dabei keine Rolle.

Definition: Grammatik

Eine Grammatik ist ein 4-Tupel G=(VN,VT,P,S)G = (V_N, V_T, P, S) mit

Die Angabe als Tupel ist die übliche Schreibweise und wird im Abitur erwartet. Sie zwingt dazu, nichts zu vergessen: vier Klammern, vier Bestandteile.

Eine Ableitung ist eine Folge von Ersetzungen, beginnend beim Startsymbol. Die Menge aller ableitbaren Wörter über VTV_T heißt die von GG erzeugte Sprache L(G)L(G).

5.4.1Ein erstes Beispiel

VT={Katzen,Hunde,schnurren,fressen},VN={S,Subjekt,Prädikat}V_T = \{\text{Katzen}, \text{Hunde}, \text{schnurren}, \text{fressen}\}, \quad V_N = \{S, \text{Subjekt}, \text{Prädikat}\}

(P1)S→Subjekt Prädikat(P2)Subjekt→Katzen∣Hunde(P3)Prädikat→schnurren∣fressen \begin{aligned} (P_1)\quad & S \to \text{Subjekt Prädikat} \\ (P_2)\quad & \text{Subjekt} \to \text{Katzen} \mid \text{Hunde} \\ (P_3)\quad & \text{Prädikat} \to \text{schnurren} \mid \text{fressen} \end{aligned}

Der Pfeil bedeutet: Das Nichtterminal links darf durch die rechte Seite ersetzt werden, der Strich ∣\mid trennt Alternativen. Ableitung von „Hunde schnurren”:

S⇒Subjekt Prädikat⇒Hunde Prädikat⇒Hunde schnurrenS \Rightarrow \text{Subjekt Prädikat} \Rightarrow \text{Hunde Prädikat} \Rightarrow \text{Hunde schnurren}

Der Satz gehört also zu L(G)L(G) — dass Hunde nicht schnurren, ist eine Frage der Semantik und geht die Grammatik nichts an. Grafisch notiert man die Ableitung als Ableitungsbaum:

            S
           / \
     Subjekt  Prädikat
        |        |
      Hunde   schnurren

5.4.2Zweites Beispiel: Klammerterme

Gesucht ist eine Grammatik für korrekt geschachtelte Klammern wie (()) oder ((()())()).

VT={(,)},VN={S},P={S→(S)∣SS∣ε}V_T = \{(,\ )\}, \qquad V_N = \{S\}, \qquad P = \{\, S \to (S) \mid SS \mid \varepsilon \,\}

Ableitung von (())():

S⇒SS⇒(S)S⇒((S))S⇒(())S⇒(())(S)⇒(())()S \Rightarrow SS \Rightarrow (S)S \Rightarrow ((S))S \Rightarrow (())S \Rightarrow (())(S) \Rightarrow (())()

Beachten Sie die Regel S→(S)S \to (S): Das Nichtterminal steht zwischen Terminalzeichen. Diese Bauart wird in Abschnitt 5.10 entscheidend.

5.4.3Drittes Beispiel: ein Satzmuster

VT={der,den,Hund,Briefträger,beißt,schlägt}VN={S,Subjekt,Prädikat,Objekt,Nomen}P={S→Subjekt Prädikat Objekt,Subjekt→der Nomen,Objekt→den Nomen,Prädikat→beißt∣schlägt,Nomen→Hund∣Briefträger} \begin{aligned} V_T &= \{\text{der}, \text{den}, \text{Hund}, \text{Briefträger}, \text{beißt}, \text{schlägt}\} \\ V_N &= \{S, \text{Subjekt}, \text{Prädikat}, \text{Objekt}, \text{Nomen}\} \\ P &= \{\, S \to \text{Subjekt Prädikat Objekt}, \; \text{Subjekt} \to \text{der Nomen}, \; \text{Objekt} \to \text{den Nomen}, \\ &\qquad \text{Prädikat} \to \text{beißt} \mid \text{schlägt}, \; \text{Nomen} \to \text{Hund} \mid \text{Briefträger} \,\} \end{aligned}

Arbeitsauftrag 4
  1. Leiten Sie mit der letzten Grammatik die Sätze „der Briefträger beißt den Hund” und „der Briefträger schlägt den Briefträger” ab und zeichnen Sie je einen Ableitungsbaum.
  2. Wie viele verschiedene Sätze erzeugt diese Grammatik insgesamt? Begründen Sie mit einer Rechnung.
  3. Leiten Sie ((())) und ()()() mit der Klammergrammatik ab.
  4. Geben Sie eine Grammatik an, die alle Wörter aus aa und bb erzeugt, die mit aa beginnen.
  5. Erweitern Sie die Satzgrammatik um ein Adjektiv vor dem Nomen.
Lösung vergleichen
  1. Erster Satz:

    S⇒Subjekt Prädikat Objekt⇒der Nomen Prädikat Objekt⇒der Briefträger Prädikat Objekt⇒der Briefträger beißt Objekt⇒der Briefträger beißt den Nomen⇒der Briefträger beißt den Hund \begin{aligned} S &\Rightarrow \text{Subjekt Prädikat Objekt} \Rightarrow \text{der Nomen Prädikat Objekt} \\ &\Rightarrow \text{der Briefträger Prädikat Objekt} \Rightarrow \text{der Briefträger beißt Objekt} \\ &\Rightarrow \text{der Briefträger beißt den Nomen} \Rightarrow \text{der Briefträger beißt den Hund} \end{aligned}

                     S
           /         |         \
      Subjekt    Prädikat    Objekt
       /   \         |        /   \
     der  Nomen    beißt    den  Nomen
            |                      |
       Briefträger               Hund

    Zweiter Satz:

    S⇒Subjekt Prädikat Objekt⇒der Nomen Prädikat Objekt⇒der Briefträger Prädikat Objekt⇒der Briefträger schlägt Objekt⇒der Briefträger schlägt den Nomen⇒der Briefträger schlägt den Briefträger \begin{aligned} S &\Rightarrow \text{Subjekt Prädikat Objekt} \Rightarrow \text{der Nomen Prädikat Objekt} \\ &\Rightarrow \text{der Briefträger Prädikat Objekt} \Rightarrow \text{der Briefträger schlägt Objekt} \\ &\Rightarrow \text{der Briefträger schlägt den Nomen} \Rightarrow \text{der Briefträger schlägt den Briefträger} \end{aligned}

    Der Baum hat dieselbe Gestalt wie oben; an den Blättern stehen „schlägt“ und unter dem Objekt wieder „Briefträger“.

  2. 2⋅2⋅2=82 \cdot 2 \cdot 2 = 8 Sätze: Das Nomen im Subjekt hat 2 Möglichkeiten, das Prädikat 2 und das Nomen im Objekt wieder 2. Alle anderen Regeln haben nur eine Alternative.

  3. S⇒(S)⇒((S))⇒(((S)))⇒((()))S \Rightarrow (S) \Rightarrow ((S)) \Rightarrow (((S))) \Rightarrow ((()))

    S⇒SS⇒SSS⇒(S)SS⇒()SS⇒()(S)S⇒()()S⇒()()(S)⇒()()()S \Rightarrow SS \Rightarrow SSS \Rightarrow (S)SS \Rightarrow ()SS \Rightarrow ()(S)S \Rightarrow ()()S \Rightarrow ()()(S) \Rightarrow ()()()

  4. Zum Beispiel VT={a,b}V_T = \{a, b\}, VN={S,A}V_N = \{S, A\}, P={S→aA∣a,A→aA∣bA∣a∣b}P = \{\, S \to aA \mid a, \; A \to aA \mid bA \mid a \mid b \,\}, Startsymbol SS. Das erste Zeichen ist immer aa, danach beliebig viele aa und bb.

  5. Im Deutschen hängt die Endung des Adjektivs vom Fall ab („der große Hund“, aber „den großen Hund“). Deshalb zwei Nichtterminale: Subjekt→der AdjN Nomen\text{Subjekt} \to \text{der AdjN Nomen}, Objekt→den AdjA Nomen\text{Objekt} \to \text{den AdjA Nomen}, AdjN→große∣kleine\text{AdjN} \to \text{große} \mid \text{kleine}, AdjA→großen∣kleinen\text{AdjA} \to \text{großen} \mid \text{kleinen}. Wer nur ein Nichtterminal Adjektiv einführt, erzeugt auch „den große Hund“ — das ist syntaktisch falsch.

5.5Reguläre Grammatiken

Diesen Abschnitt als PDF (S. 7)

Wer ein Kennzeichen wie WND-AB 123 vorliest, geht Zeichen für Zeichen von links nach rechts. Merken muss er sich dabei nur eines: ob er gerade im Kreiskürzel, bei den Buchstaben oder bei den Ziffern ist. Er blättert nie zurück und muss nichts Späteres vorwegnehmen. Grammatiken, die so gebaut sind — ein Zeichen anhängen, dann weiter —, heißen regulär.

Definition. Eine Grammatik heißt regulär, wenn jede Produktion die Form

A→xBoderA→xA \to xB \qquad \text{oder} \qquad A \to x

hat, mit A,B∈VNA, B \in V_N und x∈VTx \in V_T. Rechts steht also genau ein Terminalzeichen und dahinter höchstens ein Nichtterminal — und wenn, dann ganz rechts. Die erzeugte Sprache heißt reguläre Sprache.

Stolperstein

Die Definition ist enger, als sie beim Querlesen wirkt. Nicht erlaubt sind A→xyBA \to xyB (zwei Terminalzeichen), A→BxA \to Bx (Nichtterminal links) und A→εA \to \varepsilon (leeres Wort). Umgekehrt gilt: Eine Grammatik, die diese Form nicht hat, kann durchaus eine reguläre Sprache erzeugen — man kann sie dann in die reguläre Form umschreiben. „Regulär” ist also eine Eigenschaft der Grammatik; „reguläre Sprache” eine Eigenschaft der Sprache. Beides auseinanderzuhalten lohnt sich.

Die Klammergrammatik aus 5.4 ist nach dieser Definition nicht regulär — bei S→(S)S \to (S) steht das Nichtterminal in der Mitte. Das ist kein Zufall, wie sich zeigen wird.

Beispiel: gerade Dualzahlen. Gesucht ist eine Grammatik für alle Dualzahlen ohne führende Null, die gerade sind — die also mit 1 beginnen und auf 0 enden.

VT={0,1},VN={S,A},P={S→1A,A→0A∣1A∣0}V_T = \{0, 1\}, \quad V_N = \{S, A\}, \quad P = \{\, S \to 1A, \quad A \to 0A \mid 1A \mid 0 \,\}

Ableitung von 1010: S⇒1A⇒10A⇒101A⇒1010S \Rightarrow 1A \Rightarrow 10A \Rightarrow 101A \Rightarrow 1010

Geben Sie im Bedienfeld auch 101 ein — eine ungerade Zahl. Es gibt keine Ableitung, und das Werkzeug sagt es.

Beispiel: Bezeichner. In vielen Sprachen gilt: Ein Bezeichner beginnt mit einem Buchstaben, danach folgen beliebig viele Buchstaben oder Ziffern. Mit VT={bu,zi}V_T = \{bu, zi\} (Buchstabe, Ziffer):

VN={S,R},P={S→bu∣buR,R→buR∣ziR∣bu∣zi}V_N = \{S, R\}, \qquad P = \{\, S \to bu \mid bu\,R, \quad R \to bu\,R \mid zi\,R \mid bu \mid zi \,\}

Arbeitsauftrag 5
  1. Prüfen Sie, ob die Grammatik P={S→aS∣bS∣aaA,A→aA∣bA∣ε}P = \{S \to aS \mid bS \mid aaA, \; A \to aA \mid bA \mid \varepsilon\} die obige Definition erfüllt — prüfen Sie jede Produktion einzeln. Beschreiben Sie anschließend L(G)L(G) in Worten und geben Sie eine Grammatik an, die dieselbe Sprache erzeugt und die Definition erfüllt.
  2. Geben Sie eine reguläre Grammatik für alle ungeraden Dualzahlen an und leiten Sie 10111011 und 10011001 ab.
  3. Gibt es eine reguläre Grammatik für L={10,100,110,1000,1010,1100,1110,…}L = \{10, 100, 110, 1000, 1010, 1100, 1110, \dots\}? Beschreiben Sie die Sprache zuerst in Worten.
  4. Begründen Sie, warum S→aSbS \to aSb nicht regulär ist.
Lösung vergleichen
  1. S→aSS \to aS und S→bSS \to bS erfüllen die Definition. S→aaAS \to aaA nicht: zwei Terminalzeichen. A→aAA \to aA und A→bAA \to bA erfüllen sie, A→εA \to \varepsilon nicht: leeres Wort. L(G)L(G) ist die Menge aller Wörter über {a,b}\{a, b\}, die aaaa enthalten. Eine reguläre Grammatik dafür: P={S→aS∣bS∣aA,A→aB∣a,B→aB∣bB∣a∣b}P = \{\, S \to aS \mid bS \mid aA, \; A \to aB \mid a, \; B \to aB \mid bB \mid a \mid b \,\}. AA heißt „das erste aa des Paares ist gelesen“, BB „aaaa ist schon da“.
  2. P={S→1A∣1,A→0A∣1A∣1}P = \{\, S \to 1A \mid 1, \; A \to 0A \mid 1A \mid 1 \,\} (die Regel S→1S \to 1 erzeugt die 1). S⇒1A⇒10A⇒101A⇒1011S \Rightarrow 1A \Rightarrow 10A \Rightarrow 101A \Rightarrow 1011 und S⇒1A⇒10A⇒100A⇒1001S \Rightarrow 1A \Rightarrow 10A \Rightarrow 100A \Rightarrow 1001.
  3. Es sind alle Dualzahlen ohne führende Null, die gerade und mindestens 2 sind — sie beginnen mit 1 und enden auf 0. Ja, das ist genau die Grammatik aus dem Beispiel: P={S→1A,A→0A∣1A∣0}P = \{\, S \to 1A, \; A \to 0A \mid 1A \mid 0 \,\}.
  4. Rechts stehen zwei Terminalzeichen, und das Nichtterminal steht zwischen ihnen statt ganz rechts. Beides verbietet die Definition.

5.6Endliche Automaten

Diesen Abschnitt als PDF (S. 8–12)

Das Drehkreuz kennt genau zwei Zustände: gesperrt und frei. Halten Sie im Zustand gesperrt Ihre Karte an den Leser, wechselt es nach frei; gehen Sie hindurch, ist es wieder gesperrt. Drücken Sie gegen ein gesperrtes Drehkreuz, bleibt es gesperrt. Mehr weiß es nicht — weder, wie viele Leute heute schon durch sind, noch, wer Sie sind. Ein Türschloss mit Tastenfeld, das aufgeht, sobald die letzten drei Tasten 7, 3, 3 waren, ist übrigens genauso gebaut wie der Automat für „endet auf abb“ weiter unten.

Eine Grammatik erzeugt Wörter. Für den Compiler brauchen wir das Gegenstück: eine Maschine, die ein vorgelegtes Wort prüft. Das leistet der endliche Automat.

Definition: Endlicher Automat

Ein endlicher akzeptierender Automat (Akzeptor) ist ein 5-Tupel M=(Z,A,f,z0,F)M = (Z, A, f, z_0, F) mit

Der Automat akzeptiert ein Wort, wenn er nach dem Lesen des letzten Zeichens in einem Endzustand steht.

Gezeichnet wird er als Zustandsgraph: Zustände sind Kreise, Übergänge beschriftete Pfeile, der Startzustand hat einen Pfeil von außen, Endzustände einen doppelten Rand.

Beispiel: Wörter über {a,b}\{a, b\}, die aa enthalten.

Zustandsgraph: akzeptiert alle Wörter über \{a,b\}, die aa enthalten.

In Worten: z0z_0 heißt „das zuletzt gelesene Zeichen war kein aa“, z1z_1 heißt „das zuletzt gelesene Zeichen war ein aa, aber noch kein aaaa”, und z2z_2 heißt „aaaa ist aufgetreten” — dieser Zustand wird nie wieder verlassen. Ein bb in z1z_1 wirft zurück nach z0z_0. Beachten Sie: In z0z_0 kann der Automat schon beliebig viele aa gelesen haben, nur eben nicht als letztes Zeichen. Der Zustand merkt sich nicht die Anzahl, sondern allein, wie weit das gesuchte aaaa gerade gediehen ist.

Dieselbe Information als Übergangstabelle — die Form, die man zum Programmieren braucht:

Zustand bei aa bei bb Endzustand
z0z_0 z1z_1 z0z_0 nein
z1z_1 z2z_2 z0z_0 nein
z2z_2 z2z_2 z2z_2 ja

Beispiel: Wörter über {a,b}\{a, b\}, die auf abb enden.

Jeder Zustand merkt sich, wie viel vom gesuchten abb schon gelesen ist.
Zustand bei aa bei bb Bedeutung Endzustand
z0z_0 z1z_1 z0z_0 nichts Passendes gesehen nein
z1z_1 z1z_1 z2z_2 zuletzt aa nein
z2z_2 z1z_1 z3z_3 zuletzt abab nein
z3z_3 z1z_1 z0z_0 zuletzt abbabb ja

Der Zustand merkt sich also gerade so viel von der Vergangenheit, wie für die Entscheidung nötig ist — und keinen Buchstaben mehr. Das ist die zentrale Idee: Der Zustand ist das Gedächtnis des Automaten, und dieses Gedächtnis ist endlich.

Dasselbe Muster an einer Tür: Das Tastenschloss merkt sich nur, wie viel vom Code zuletzt getippt wurde. Alle Ziffern außer 7 und 3 stehen am Pfeil als „sonst“.

Arbeitsauftrag 6
  1. Zeichnen Sie den Zustandsgraphen zur zweiten Tabelle und prüfen Sie die Wörter abb, aabb, abba, babb.
  2. Konstruieren Sie einen DEA für alle geraden Dualzahlen und einen für alle ungeraden.
  3. Konstruieren Sie einen DEA für Bezeichner nach der Regel aus 5.5.
  4. Konstruieren Sie einen DEA über {a,b}\{a, b\}, der genau die Wörter mit einer geraden Anzahl von aa akzeptiert.
  5. Geben Sie zu Ihrem Automaten aus Aufgabe 24 die Übergangstabelle an.
  6. Welche Sprache akzeptiert der Automat mit Z={z0,z1}Z = \{z_0, z_1\}, F={z1}F = \{z_1\} und den Übergängen f(z0,0)=z0f(z_0, 0) = z_0, f(z0,1)=z1f(z_0, 1) = z_1, f(z1,0)=z1f(z_1, 0) = z_1, f(z1,1)=z0f(z_1, 1) = z_0? (Tipp: Zählen Sie.)
Lösung vergleichen
  1. Der Graph hat vier Zustände; z0z_0 ist Startzustand, z3z_3 Endzustand, die Pfeile stehen in der Tabelle. Die Läufe:

    Wort Zustandsfolge Ergebnis
    abb z0,z1,z2,z3z_0, z_1, z_2, z_3 akzeptiert
    aabb z0,z1,z1,z2,z3z_0, z_1, z_1, z_2, z_3 akzeptiert
    abba z0,z1,z2,z3,z1z_0, z_1, z_2, z_3, z_1 abgelehnt
    babb z0,z0,z1,z2,z3z_0, z_0, z_1, z_2, z_3 akzeptiert
  2. Fehlende Übergänge führen jeweils in einen Fehlerzustand.

    Gerade Dualzahlen (Endzustand EE):

    Zustand bei 0 bei 1 Endzustand
    SS – AA nein
    AA EE AA nein
    EE EE AA ja

    Ungerade Dualzahlen (Endzustand UU):

    Zustand bei 0 bei 1 Endzustand
    SS – UU nein
    UU AA UU ja
    AA AA UU nein
  3. Mit dem Alphabet {bu,zi}\{bu, zi\}:

    Zustand bei bubu bei zizi Endzustand
    SS RR – nein
    RR RR RR ja
  4. Zwei Zustände: gg („bisher gerade viele aa“, Start- und Endzustand) und uu. Ein aa wechselt den Zustand, ein bb lässt ihn stehen. Das leere Wort wird akzeptiert — null ist gerade.

  5. Übergangstabelle (→\to markiert den Startzustand):

    Zustand bei aa bei bb Endzustand
    →g\to g uu gg ja
    uu gg uu nein
  6. Eine 1 wechselt den Zustand, eine 0 nicht. Der Automat steht also genau dann in z1z_1, wenn er ungerade viele Einsen gelesen hat: Er akzeptiert alle Wörter über {0,1}\{0, 1\} mit einer ungeraden Anzahl von Einsen.

5.6.1Deterministisch oder nichtdeterministisch

Sie suchen in einem fremden Einkaufszentrum einen bestimmten Laden. Allein müssten Sie an jeder Gabelung raten. Mit genug Freunden geht es ohne Raten: An jeder Gabelung geht jemand in jede Richtung, und wer ankommt, ruft die anderen. Ein nichtdeterministischer Automat rechnet genau so — er verfolgt alle Wege gleichzeitig und ist zufrieden, wenn irgendeiner ankommt.

Beim NEA ist ff also keine Funktion in den Zuständen, sondern eine in die Teilmengen von ZZ: f:Z×A→𝒫(Z)f: Z \times A \to \mathcal{P}(Z). Der Automat ist gewissermaßen in mehreren Zuständen gleichzeitig.

NEAs sind oft schneller hingeschrieben — bauen lässt sich aber nur ein DEA, denn eine Maschine kann nicht raten. Der Trost ist ein Satz:

Merke

Zu jedem NEA gibt es einen DEA, der dieselbe Sprache akzeptiert. Nichtdeterminismus bringt keine zusätzliche Mächtigkeit, nur kürzere Diagramme.

5.6.2Die Teilmengenkonstruktion

Der Beweis des Satzes ist zugleich ein Bauplan. Die Idee: Wenn der NEA in mehreren Zuständen gleichzeitig sein kann, macht man jede mögliche Zustandsmenge zu einem einzigen DEA-Zustand.

Definition: Teilmengenkonstruktion

Gegeben ein NEA mit Zustandsmenge ZZ. Der zugehörige DEA entsteht so:

  1. Startzustand des DEA ist die Menge {z0}\{z_0\}.
  2. Für jede bereits erzeugte Menge MM und jedes Zeichen cc bildet man die Menge aller Zustände, die der NEA von irgendeinem Zustand aus MM mit cc erreichen kann. Das ist der Folgezustand.
  3. Neu entstandene Mengen werden genauso behandelt, bis keine neue mehr auftritt.
  4. Endzustände des DEA sind genau die Mengen, die mindestens einen Endzustand des NEA enthalten.
Beispiel: Wörter über {a, b}, die auf ab enden

Der NEA rät, wann das letzte ab beginnt:

Der NEA. In z_0 hat er bei a zwei Möglichkeiten — das ist der Nichtdeterminismus.
a b
z0z_0 {z0,z1}\{z_0, z_1\} {z0}\{z_0\}
z1z_1 ∅\emptyset {z2}\{z_2\}
z2z_2 ∅\emptyset ∅\emptyset

Endzustand ist z2z_2. In z0z_0 ist der Automat nichtdeterministisch: Bei a kann er dort bleiben oder nach z1z_1 wechseln.

Im Simulator sehen Sie die Zustandsmenge wandern — genau das, was die Teilmengenkonstruktion gleich zu einzelnen Zuständen zusammenfasst:

Durchführung. Start ist A={z0}A = \{z_0\}.

Menge mit a mit b
A={z0}A = \{z_0\} {z0,z1}=B\{z_0, z_1\} = B {z0}=A\{z_0\} = A
B={z0,z1}B = \{z_0, z_1\} {z0,z1}=B\{z_0, z_1\} = B {z0,z2}=C\{z_0, z_2\} = C
C={z0,z2}C = \{z_0, z_2\} {z0,z1}=B\{z_0, z_1\} = B {z0}=A\{z_0\} = A

Keine neue Menge mehr — fertig. CC enthält z2z_2 und ist damit der einzige Endzustand.

Der fertige DEA:

Der konstruierte DEA. Über jedem Zustand steht die Menge von NEA-Zuständen, aus der er entstanden ist.

Übergangstabelle des DEA:

a b
→A\to A BB AA
BB BB CC
C*C^{*} BB AA

Probe: bab läuft A→A→B→CA \to A \to B \to C — akzeptiert. aba läuft A→B→C→BA \to B \to C \to B — abgelehnt, richtig, denn aba endet nicht auf ab.

Merke

Hat der NEA nn Zustände, hat der DEA höchstens 2n2^n — so viele Teilmengen gibt es. Meist sind es weit weniger, weil die meisten Mengen nie erreicht werden. Im Beispiel waren es 3 statt der möglichen 8.

Arbeitsauftrag 7
  1. Konstruieren Sie mit der Teilmengenkonstruktion einen DEA zu dem NEA über {0,1}\{0,1\} mit f(z0,0)={z0,z1}f(z_0,0) = \{z_0,z_1\}, f(z0,1)={z0}f(z_0,1) = \{z_0\}, f(z1,1)={z2}f(z_1,1) = \{z_2\}, F={z2}F = \{z_2\}. Welche Sprache akzeptiert er?
  2. Geben Sie zum DEA aus dem Beispiel das 5-Tupel vollständig an.
  3. Zeichnen Sie einen NEA, der alle Wörter über {a,b}\{a,b\} akzeptiert, die aa oder bb enthalten, und wandeln Sie ihn um. Wie viele Zustände hat der DEA?
Lösung vergleichen
  1. Start ist A={z0}A = \{z_0\}:

    Menge mit 0 mit 1
    A={z0}A = \{z_0\} {z0,z1}=B\{z_0, z_1\} = B {z0}=A\{z_0\} = A
    B={z0,z1}B = \{z_0, z_1\} {z0,z1}=B\{z_0, z_1\} = B {z0,z2}=C\{z_0, z_2\} = C
    C={z0,z2}C = \{z_0, z_2\} {z0,z1}=B\{z_0, z_1\} = B {z0}=A\{z_0\} = A

    Endzustand ist CC. Der Automat akzeptiert alle Wörter über {0,1}\{0, 1\}, die auf 01 enden — dasselbe Muster wie im Beispiel, mit 0 statt aa und 1 statt bb.

  2. M=({A,B,C},{a,b},f,A,{C})M = (\{A, B, C\},\; \{a, b\},\; f,\; A,\; \{C\}) mit f(A,a)=Bf(A,a) = B, f(A,b)=Af(A,b) = A, f(B,a)=Bf(B,a) = B, f(B,b)=Cf(B,b) = C, f(C,a)=Bf(C,a) = B, f(C,b)=Af(C,b) = A.

  3. Ein NEA mit vier Zuständen: ss (Start), pp („ein aa gelesen“), qq („ein bb gelesen“) und ee (Endzustand). f(s,a)={s,p}f(s,a) = \{s, p\}, f(s,b)={s,q}f(s,b) = \{s, q\}, f(p,a)={e}f(p,a) = \{e\}, f(q,b)={e}f(q,b) = \{e\}, f(e,a)=f(e,b)={e}f(e,a) = f(e,b) = \{e\}. Die Teilmengenkonstruktion:

    Menge mit aa mit bb Endzustand
    A={s}A = \{s\} BB CC nein
    B={s,p}B = \{s, p\} DD CC nein
    C={s,q}C = \{s, q\} BB EE nein
    D={s,p,e}D = \{s, p, e\} DD EE ja
    E={s,q,e}E = \{s, q, e\} DD EE ja

    Der DEA hat 5 Zustände. DD und EE verhalten sich gleich — beide Endzustände, beide gehen bei aa nach DD und bei bb nach EE. Fasst man sie zusammen, bleiben 4.

5.7Automaten mit Ausgabe

Diesen Abschnitt als PDF (S. 13–16)

Der GK-Lehrplan nennt ausdrücklich „endliche Automaten ohne Ausgabe”. Mealy- und Moore-Automaten samt Ausgabetabelle stehen nur im LK-Lehrplan — dort sogar mit genau dem Beispiel, das hier durchgerechnet wird: Erzeuger und Prüfer eines Paritätsbits.

Bisher konnte unser Automat nur eines: am Ende ja oder nein sagen. Ein Getränkeautomat tut mehr — er gibt Wechselgeld heraus, schaltet eine Lampe ein, wirft eine Flasche aus. Solche Maschinen liefern während des Lesens Ausgaben.

Der Akzeptor ist dafür der Sonderfall: ein Automat, dessen einzige Ausgabe die Antwort am Schluss ist. Die allgemeine Form hat ein Ausgabealphabet dazu.

Definition: Mealy- und Moore-Automat

Ein endlicher Automat mit Ausgabe ist ein 6-Tupel M=(Z,A,B,f,g,z0)M = (Z, A, B, f, g, z_0): Zu Zustandsmenge, Eingabealphabet, Übergangsfunktion und Anfangszustand kommen ein Ausgabealphabet BB und eine Ausgabefunktion gg hinzu. Eine Finalmenge FF gibt es nicht — die Antwort steckt in der Ausgabe, nicht im Zustand am Ende. Zwei Bauarten unterscheiden sich darin, woran die Ausgabe hängt:

Beide sind gleich mächtig: Zu jedem Mealy-Automaten gibt es einen Moore-Automaten mit derselben Wirkung und umgekehrt. Der Mealy-Automat kommt dabei meist mit weniger Zuständen aus, der Moore-Automat ist leichter zu lesen.

Eine Ampel ist ein Moore-Automat: Welche Lampen leuchten, hängt allein an ihrem Zustand, und der Takt schaltet sie von Phase zu Phase. Der Getränkeautomat verhält sich wie ein Mealy-Automat: Die Flasche fällt in dem Moment, in dem die letzte Münze eingeworfen wird — die Ausgabe gehört zum Übergang, nicht zum Zustand.

5.7.1Beispiel: ein Paritätsbit erzeugen

Beim Übertragen von Daten hängt man oft ein Paritätsbit an: ein zusätzliches Bit, das so gewählt wird, dass die Gesamtzahl der Einsen gerade ist. Kippt unterwegs ein einzelnes Bit, stimmt die Rechnung nicht mehr und der Fehler fällt auf.

Der Erzeuger braucht dafür genau zwei Zustände — mehr muss er sich nicht merken:

Mealy-Automat zur Erzeugung des Paritätsbits. Am Pfeil steht Eingabe / Ausgabe.

Die Ausgabe ist jeweils die Parität nach dem gelesenen Zeichen. Das zuletzt ausgegebene Bit ist damit das gesuchte Paritätsbit.

Dieselbe Information als Übergangs- und Ausgabetabelle:

Zustand bei 0 Ausgabe bei 1 Ausgabe
gg (gerade) gg 0 uu 1
uu (ungerade) uu 1 gg 0
Beispiel: Das Datenwort 1011
gelesen 1 0 1 1
Zustand gg uu uu gg uu
Ausgabe 1 1 0 1

Das letzte Ausgabebit ist 1 — gesendet wird also 10111. Die Probe: 10111 enthält vier Einsen, und vier ist gerade.

Derselbe Automat als Moore-Maschine. Die Ausgabe wandert vom Pfeil in den Zustand:

Moore-Automat für dieselbe Aufgabe.

Die Tabelle wird dadurch schmaler — die Ausgabespalte gehört jetzt zum Zustand, nicht zum Übergang:

Zustand Ausgabe bei 0 bei 1
gg (gerade) 0 gg uu
uu (ungerade) 1 uu gg
Stolperstein

Zählen Sie die Ausgaben nach: Der Mealy-Automat liefert zu 1011 die vier Bits 1,1,0,11,1,0,1 — eines pro gelesenem Zeichen. Der Moore-Automat liefert fünf, nämlich 0,1,1,0,10,1,1,0,1: Er gibt schon im Anfangszustand aus, bevor überhaupt ein Zeichen gelesen ist. Das letzte Bit ist in beiden Fällen dasselbe und damit das gesuchte Paritätsbit; bei einem Wort der Länge nn hat ein Mealy-Automat aber nn Ausgaben und ein Moore-Automat n+1n+1. „Gleich mächtig” heißt also nicht „Ausgabe für Ausgabe gleich”.

5.7.2Beispiel: das Paritätsbit prüfen

Auf der Empfängerseite genügt wieder ein Akzeptor — hier interessiert nur ja oder nein. Er liest Datenwort und Paritätsbit und akzeptiert, wenn die Zahl der Einsen gerade ist:

M=({g,u},{0,1},f,g,{g})mitf(g,0)=g,f(g,1)=u,f(u,0)=u,f(u,1)=gM = (\{g, u\},\; \{0,1\},\; f,\; g,\; \{g\}) \quad\text{mit}\quad f(g,0)=g,\ f(g,1)=u,\ f(u,0)=u,\ f(u,1)=g

Vergleichen Sie ihn mit dem Automaten aus Aufgabe 26: Dieselben Übergänge, aber der jeweils andere Zustand ist Endzustand. Zwei Automaten, die sich nur in der Finalmenge unterscheiden, akzeptieren genau die zueinander komplementären Sprachen.

Merke

Erzeuger und Prüfer haben denselben Zustandsgraphen. Der Unterschied liegt allein darin, was man von ihm will: Der Erzeuger gibt bei jedem Schritt etwas aus, der Prüfer sagt am Ende nur, ob er in einem Endzustand steht.

Stolperstein

Ein Paritätsbit erkennt einen gekippten Bitfehler sicher. Kippen zwei Bits, ist die Parität wieder in Ordnung und der Fehler bleibt unentdeckt. Und korrigieren kann es gar nichts — es sagt nur, dass etwas falsch ist, nicht was.

Arbeitsauftrag 8
  1. Lassen Sie den Erzeuger auf 1101 und 0000 laufen. Notieren Sie Zustände und Ausgaben wie in der Tabelle oben. Welches Paritätsbit wird angehängt?
  2. Prüfen Sie mit dem Prüfer die Wörter 10111, 10011 und 11011. Welche sind unterwegs verfälscht worden?
  3. Zeichnen Sie einen Mealy-Automaten für einen Getränkeautomaten, der 50-Cent- und 1-Euro-Stücke annimmt und bei 1,50 € eine Flasche ausgibt. Was gibt er bei 2 € aus?
  4. Ein Moore-Automat gibt bei jedem gelesenen Zeichen aus, ob die bisher gelesene Zeichenzahl gerade ist. Zeichnen Sie ihn.
  5. Geben Sie denselben Automaten als Mealy-Automat an. Wie viele Ausgaben liefern die beiden zu einem Wort der Länge 6?
  6. Begründen Sie, warum der Akzeptor ein Sonderfall des Automaten mit Ausgabe ist.
Lösung vergleichen
  1. Für 1101:

    gelesen 1 1 0 1
    Zustand gg uu gg gg uu
    Ausgabe 1 0 0 1

    Paritätsbit 1, gesendet wird 11011. Für 0000:

    gelesen 0 0 0 0
    Zustand gg gg gg gg gg
    Ausgabe 0 0 0 0

    Paritätsbit 0, gesendet wird 00000.

  2. 10111 hat vier Einsen, 11011 ebenfalls — beide enden in gg und sind in Ordnung. 10011 hat drei Einsen, endet in uu und ist verfälscht.

  3. Die Zustände merken sich das Guthaben: 00, 5050 und 100100 Cent; Start ist 00.

    Zustand bei 50 ct Ausgabe bei 1 € Ausgabe
    00 5050 – 100100 –
    5050 100100 – 00 Flasche
    100100 00 Flasche 00 Flasche + 50 ct

    Bei 2 € in zwei 1-€-Stücken gibt er eine Flasche und 50 ct Wechselgeld aus. Bei vier 50-ct-Stücken kommt die Flasche schon nach der dritten Münze; die vierte bleibt als Guthaben von 50 ct stehen.

  4. Zwei Zustände, die Ausgabe steht im Kreis: gg / „ja“ (Start) und uu / „nein“. Jedes gelesene Zeichen wechselt den Zustand.

  5. Als Mealy-Automat stehen die Ausgaben am Übergang: g→x/neinug \xrightarrow{x / \text{nein}} u und u→x/jagu \xrightarrow{x / \text{ja}} g für jedes Zeichen xx. Zu einem Wort der Länge 6 liefert der Mealy-Automat 6 Ausgaben, der Moore-Automat 7 — er gibt schon vor dem ersten Zeichen aus.

  6. Ein Akzeptor ist ein Moore-Automat mit dem Ausgabealphabet {ja,nein}\{\text{ja}, \text{nein}\}: g(z)=jag(z) = \text{ja} genau für z∈Fz \in F. Von seinen Ausgaben interessiert nur die letzte. Die Finalmenge ist also nur eine besondere Ausgabefunktion.

5.8Grammatik und Automat sind zwei Seiten derselben Sache

Diesen Abschnitt als PDF (S. 17–18)

Eine Bauanleitung für ein Klemmbausteinmodell sagt, wie man es Schritt für Schritt aufbaut. Wer ein fertiges Modell vor sich hat, kann umgekehrt Stein für Stein prüfen, ob es nach dieser Anleitung gebaut ist. Beides beschreibt dasselbe Modell, einmal erzeugend, einmal prüfend. Für reguläre Sprachen sind Grammatik und Automat genau dieses Paar.

Zwischen regulären Grammatiken und endlichen Automaten lässt sich mechanisch hin- und herübersetzen.

Von der Grammatik zum Automaten. Jedes Nichtterminal wird ein Zustand, das Startsymbol der Startzustand. Aus A→xBA \to xB wird der Übergang f(A,x)=Bf(A, x) = B. Aus A→xA \to x wird ein Übergang in einen zusätzlichen Endzustand EE.

Beispiel mit P={S→1A,A→0A∣1A∣0}P = \{S \to 1A, \; A \to 0A \mid 1A \mid 0\} (gerade Dualzahlen). Die Regeln A→0AA \to 0A und A→0A \to 0 beginnen beide mit einer 0 — der Zustand AA hat bei 0 also zwei Nachfolger:

Zustand bei 0 bei 1 Endzustand
SS – {A}\{A\} nein
AA {A,E}\{A, E\} {A}\{A\} nein
EE – – ja
Stolperstein

Die Konstruktion liefert im Allgemeinen einen NEA, keinen DEA — immer dann, wenn zu einem Nichtterminal zwei Regeln mit demselben Terminalzeichen gehören. Das ist kein Mangel: Mit der Teilmengenkonstruktion aus 5.6.2 wird daraus ein DEA.

Hier von Hand nachgebaut: Aus {A,E}\{A, E\} wird ein DEA-Zustand, den wir E′E' nennen. Er ist Endzustand, weil er EE enthält, und verhält sich sonst wie AA:

Zustand bei 0 bei 1 Endzustand
SS – AA nein
AA E′E' AA nein
E′E' E′E' AA ja

Probe: 10101010 läuft S→A→E′→A→E′S \to A \to E' \to A \to E' — akzeptiert. 10111011 endet in AA und wird abgelehnt, richtig, denn 1011 ist ungerade.

Stolperstein

In der Tabelle steht bei SS und der 0 ein Strich: Dieser Übergang kommt in der Grammatik nicht vor, weil keine Dualzahl mit 0 beginnt. Streng genommen verlangt die Definition aus 5.6 aber eine auf ganz Z×AZ \times A definierte Übergangsfunktion. Man ergänzt deshalb einen zusätzlichen Fehlerzustand zFz_F, der nie Endzustand ist und alle Zeichen auf sich selbst abbildet; jeder Strich führt dorthin. Gezeichnet wird er meist weggelassen, weil er das Bild unübersichtlich macht. Im Programm später entspricht ihm der Zweig „Übergang nicht in der Tabelle → abweisen”.

Vom Automaten zur Grammatik. Umgekehrt wird jeder Zustand ein Nichtterminal, der Startzustand das Startsymbol. Aus f(Z1,x)=Z2f(Z_1, x) = Z_2 wird die Produktion Z1→xZ2Z_1 \to x Z_2 — und ist Z2Z_2 ein Endzustand, so kommt zusätzlich die abschließende Regel Z1→xZ_1 \to x hinzu.

Die naheliegende Abkürzung Z→εZ \to \varepsilon für jeden Endzustand wäre bequem, ist nach unserer Definition aus 5.5 aber nicht erlaubt: Dort darf rechts nur xBxB oder xx stehen, niemals das leere Wort. Deshalb der Umweg über die zusätzliche Regel.

Merke

Reguläre Grammatik, endlicher Automat und regulärer Ausdruck (Abschnitt 5.11) beschreiben genau dieselbe Klasse von Sprachen — die regulären Sprachen. Drei Schreibweisen, ein Begriff.

Ein Sonderfall bleibt: Nach unserer Definition erzeugt jede Produktion mindestens ein Zeichen, das leere Wort ε\varepsilon ist also in keiner so erzeugten Sprache enthalten. Ein Automat kann es dagegen akzeptieren — nämlich dann, wenn sein Startzustand ein Endzustand ist. Für diesen einen Fall erlaubt man zusätzlich die Regel S→εS \to \varepsilon für das Startsymbol. Mit ihr stimmen die drei Beschreibungen dann ohne Ausnahme überein.

5.9Einen Automaten programmieren

Diesen Abschnitt als PDF (S. 19–20)

Die Wache in einem Schleichspiel patrouilliert, bis sie Sie sieht. Dann verfolgt sie Sie; verliert sie Sie aus den Augen, sucht sie eine Weile und kehrt schließlich zur Patrouille zurück. Spieleentwickler programmieren solches Verhalten sehr oft als endlichen Automaten: eine Variable für den Zustand, eine Tabelle für die Übergänge. Wie wenig Code das ist, zeigt dieser Abschnitt.

Die Übergangstabelle lässt sich unmittelbar in Code übersetzen. Das Programm hält nur eine einzige Variable fest: den aktuellen Zustand.

Python

# Automat: akzeptiert alle Woerter ueber {a, b}, die "aa" enthalten
UEBERGAENGE = {
    ("z0", "a"): "z1", ("z0", "b"): "z0",
    ("z1", "a"): "z2", ("z1", "b"): "z0",
    ("z2", "a"): "z2", ("z2", "b"): "z2",
}
START = "z0"
ENDZUSTAENDE = {"z2"}


def akzeptiert(wort):
    zustand = START
    for zeichen in wort:
        if (zustand, zeichen) not in UEBERGAENGE:
            return False                      # Zeichen nicht im Alphabet
        zustand = UEBERGAENGE[(zustand, zeichen)]
    return zustand in ENDZUSTAENDE


for wort in ["abab", "abba", "baab", "aa", ""]:
    print(wort, akzeptiert(wort))

Object Pascal

program Automat;

type
  TZustand = (z0, z1, z2);

function Uebergang(zustand: TZustand; zeichen: Char): TZustand;
begin
  Result := zustand;
  case zustand of
    z0: if zeichen = 'a' then Result := z1 else Result := z0;
    z1: if zeichen = 'a' then Result := z2 else Result := z0;
    z2: Result := z2;                        { Endzustand bleibt erhalten }
  end;
end;

function Akzeptiert(const wort: string): Boolean;
var
  zustand: TZustand;
  i: Integer;
begin
  zustand := z0;
  for i := 1 to Length(wort) do
    zustand := Uebergang(zustand, wort[i]);
  Result := zustand = z2;
end;

begin
  WriteLn(Akzeptiert('abab'));               { False }
  WriteLn(Akzeptiert('baab'));               { True  }
end.

Beachten Sie den Unterschied im Aufbau: Python hält die Tabelle als Datenstruktur, Pascal als case-Verzweigung. Die Datenstruktur ist der bessere Weg — man kann einen anderen Automaten einsetzen, ohne den Code zu ändern.

Arbeitsauftrag 9
  1. Erweitern Sie das Python-Programm so, dass es den durchlaufenen Zustandsweg ausgibt.
  2. Ersetzen Sie die Tabelle durch die Ihres Automaten für „endet auf abb” und testen Sie.
  3. Schreiben Sie die Pascal-Fassung so um, dass sie eine Übergangstabelle als Array array[TZustand, 'a'..'b'] of TZustand benutzt statt der case-Anweisung.
  4. Schreiben Sie ein Programm, das einen Text zeichenweise liest und prüft, ob er ein gültiger Bezeichner ist.
  5. Projekt: Ein Programm liest eine Übergangstabelle aus einer Textdatei und prüft dann beliebige Wörter. Damit haben Sie einen Automaten-Simulator geschrieben.
Lösung vergleichen
  1. Der Weg wird in einer Liste gesammelt und am Ende ausgegeben:

    def akzeptiert(wort):
        zustand = START
        weg = [zustand]
        for zeichen in wort:
            if (zustand, zeichen) not in UEBERGAENGE:
                print(" -> ".join(weg), "-> Fehler")
                return False
            zustand = UEBERGAENGE[(zustand, zeichen)]
            weg.append(zustand)
        print(" -> ".join(weg))
        return zustand in ENDZUSTAENDE

    Für baab erscheint z0 -> z0 -> z1 -> z2 -> z2 und dann baab True.

  2. Nur die drei Konstanten ändern sich, akzeptiert bleibt, wie es ist:

    UEBERGAENGE = {
        ("z0", "a"): "z1", ("z0", "b"): "z0",
        ("z1", "a"): "z1", ("z1", "b"): "z2",
        ("z2", "a"): "z1", ("z2", "b"): "z3",
        ("z3", "a"): "z1", ("z3", "b"): "z0",
    }
    START = "z0"
    ENDZUSTAENDE = {"z3"}

    Test: abb, aabb und babb ergeben True, abba, ab und abbb ergeben False.

  3. Die Tabelle wird eine Konstante, die Schleife liest nur noch nach:

    const
      F: array[TZustand, 'a'..'b'] of TZustand = (
        (z1, z0),     { z0 bei a, bei b }
        (z2, z0),     { z1 }
        (z2, z2)      { z2 }
      );
    
    function Akzeptiert(const wort: string): Boolean;
    var
      zustand: TZustand;
      i: Integer;
    begin
      zustand := z0;
      for i := 1 to Length(wort) do
      begin
        if not (wort[i] in ['a'..'b']) then
          Exit(False);                       { Zeichen nicht im Alphabet }
        zustand := F[zustand, wort[i]];
      end;
      Result := zustand = z2;
    end;

    Die Prüfung auf das Alphabet ist nötig: Ein Zeichen außerhalb von 'a'..'b' wäre sonst ein Zugriff außerhalb des Arrays.

  4. Erst wird jedes Zeichen einer Art zugeordnet, dann läuft der Automat aus Aufgabe 23:

    def art(zeichen):
        if zeichen.isascii() and zeichen.isalpha():
            return "bu"
        if zeichen.isdigit():
            return "zi"
        return None
    
    
    UEBERGAENGE = {("S", "bu"): "R", ("R", "bu"): "R", ("R", "zi"): "R"}
    
    
    def ist_bezeichner(text):
        zustand = "S"
        for zeichen in text:
            zustand = UEBERGAENGE.get((zustand, art(zeichen)))
            if zustand is None:
                return False
        return zustand == "R"

    zaehler und x1 sind gültig, 2fast, mein wert und der leere Text nicht.

  5. Ein mögliches Dateiformat: eine Zeile start z0, eine Zeile ende z3, danach je Übergang eine Zeile von zeichen nach, also etwa z0 a z1. Das Programm liest die Datei in dasselbe Wörterbuch wie oben:

    def lade(dateiname):
        uebergaenge, start, ende = {}, None, set()
        with open(dateiname, encoding="utf-8") as datei:
            for zeile in datei:
                teile = zeile.split("#")[0].split()
                if not teile:
                    continue
                if teile[0] == "start":
                    start = teile[1]
                elif teile[0] == "ende":
                    ende = set(teile[1:])
                else:
                    von, zeichen, nach = teile
                    uebergaenge[(von, zeichen)] = nach
        return uebergaenge, start, ende

    Mit der Tabelle für „endet auf abb“ in der Datei liefert der Simulator dieselben Ergebnisse wie Aufgabe 37 — ohne dass eine Zeile Code geändert wurde.

5.10Wo endliche Automaten scheitern

Diesen Abschnitt als PDF (S. 21–22)

Die Chomsky-Hierarchie und die Beispiele nicht-regulärer und nicht-kontextfreier Sprachen stehen nur im LK-Lehrplan. Im Grundkurs genügt die Einsicht aus dem ersten Absatz: Der Zustand eines endlichen Automaten ist sein ganzes Gedächtnis, und das ist endlich.

Ein Türsteher soll am Ende des Abends sagen, ob alle Gäste wieder draußen sind. Mit einer Strichliste ist das leicht. Darf er sich aber nur merken, ob „wenig“, „mittel“ oder „viel“ los ist, kann er es nicht — egal, wie aufmerksam er ist. Genau in dieser Lage ist ein endlicher Automat: Er hat nur endlich viele Zustände, die Gästeschlange ist aber beliebig lang.

Konstruieren Sie einen Automaten, der genau die Wörter anbna^n b^n akzeptiert, also abab, aabbaabb, aaabbbaaabbb und so weiter — gleich viele aa wie bb.

Es gelingt nicht, und der Grund ist grundsätzlich: Der Automat müsste sich merken, wie viele aa er gelesen hat, bevor das erste bb kommt. Diese Zahl ist unbeschränkt, seine Zustandsmenge aber endlich. Bei genügend langer Eingabe muss er zwangsläufig zweimal in denselben Zustand geraten, obwohl er unterschiedlich viele aa gesehen hat — und dann kann er die beiden Fälle nicht mehr unterscheiden.

Dasselbe gilt für die Klammersprache aus 5.4: Verschachtelte Klammern erfordern ein unbeschränktes Gedächtnis. Genau deshalb war jene Grammatik nicht regulär.

Eine Maschine, die anbna^n b^n sehr wohl erkennt, kennen Sie schon: die Turingmaschine aus Abschnitt 1.2. Sie streicht Paare durch und schreibt sich die Zwischenstände aufs Band. Der Unterschied ist genau dieser Schreibplatz — der endliche Automat hat keinen.

Merke

Endliche Automaten erkennen genau die regulären Sprachen. Alles, was Zählen oder Schachteln erfordert, liegt außerhalb.

Für solche Sprachen braucht man mächtigere Maschinen. Ein Kellerautomat besitzt zusätzlich einen Stapelspeicher: Bei jedem aa legt er eine Marke ab, bei jedem bb nimmt er eine weg — und akzeptiert, wenn der Stapel am Ende leer ist. Damit erkennt er die kontextfreien Sprachen, zu denen auch die Klammerstrukturen der Programmiersprachen gehören. Ganz oben steht die Turingmaschine aus Abschnitt 1.2. Diese Staffelung heißt Chomsky-Hierarchie:

Typ Sprachklasse Maschine Form der Produktionen Beispiel
3 regulär endlicher Automat A→xBA \to xB oder A→xA \to x Bezeichner, Zahlen
2 kontextfrei Kellerautomat A→αA \to \alpha (links ein Nichtterminal) anbna^n b^n, Klammern
1 kontextsensitiv linear beschränkter Automat α→β\alpha \to \beta mit |α|≤|β||\alpha| \le |\beta| anbncna^n b^n c^n
0 rekursiv aufzählbar Turingmaschine beliebig haltende Programme

In Worten, von der schwächsten zur mächtigsten Stufe:

Die vier Klassen sind echt ineinander geschachtelt — jede Stufe kann alles, was die vorige kann, und mehr:

Typ 3⊊Typ 2⊊Typ 1⊊Typ 0\text{Typ 3} \subsetneq \text{Typ 2} \subsetneq \text{Typ 1} \subsetneq \text{Typ 0}

Zwei Beispiele markieren die beiden Sprünge, die in der Schule am häufigsten gebraucht werden:

Merke

L1={anbn∣n≥1}L_1 = \{a^n b^n \mid n \ge 1\} ist nicht regulär, aber kontextfrei. Der Grund steht oben: Ein endlicher Automat kann die aa nicht zählen, ein Kellerautomat schon.

L2={anbncn∣n≥1}L_2 = \{a^n b^n c^n \mid n \ge 1\} ist nicht kontextfrei, aber kontextsensitiv. Hier reicht auch der Stapel nicht: Beim Abarbeiten der bb wird er geleert — für die cc ist die Zahl der aa dann verloren. Man müsste zweimal dasselbe zählen, und dafür braucht es ein Band statt eines Stapels.

Das erklärt nebenbei den Aufbau eines Compilers: Der Lexer erkennt Token — die sind regulär, ein endlicher Automat genügt. Der Parser prüft die Struktur — die ist kontextfrei und braucht einen Stapel.

Arbeitsauftrag 10
  1. Versuchen Sie, einen Automaten für anbna^n b^n mit höchstens fünf Zuständen zu bauen. Beschreiben Sie, woran es scheitert, und geben Sie ein Wort an, das Ihr Automat fälschlich akzeptiert.
  2. Begründen Sie, warum ein Automat mit 100 Zuständen die Sprache anbna^n b^n für n≤40n \le 40 korrekt entscheiden kann — und warum das nichts nützt.
  3. Ordnen Sie ein: Telefonnummern, korrekt geklammerte Terme, Datumsangaben im Format TT.MM.JJJJ, vollständige Pascal-Programme.
Lösung vergleichen
  1. Ein naheliegender Versuch: Zustände ss, AA („nur aa gelesen“), BB („aa und danach bb gelesen“, Endzustand) und ein Fehlerzustand. Er prüft nur die Form a…ab…ba\ldots ab\ldots b, nicht die Anzahl — aab wird fälschlich akzeptiert. Das gilt für jeden Versuch mit fünf Zuständen: Unter den sechs Wörtern ε,a,aa,…,a5\varepsilon, a, aa, \ldots, a^5 müssen zwei, etwa aia^i und aja^j mit i<ji < j, im selben Zustand enden. Dann behandelt der Automat ajbia^j b^i genauso wie aibia^i b^i und akzeptiert es — obwohl es nicht zur Sprache gehört.
  2. Der Automat kann für jede Zahl von aa bis 40 einen eigenen Zustand haben (41 Zustände), dann für jeden noch fehlenden Rest an bb einen (40 Zustände, der letzte ist Endzustand), dazu einen Fehlerzustand — 82 Zustände, das passt in 100. Nur nützt es nichts: Die Sprache ist unendlich. a41b41a^{41} b^{41} gehört dazu und wird abgelehnt, und jede größere Schranke hat dasselbe Problem.
  3. Telefonnummern: regulär — Ziffern, Trennzeichen, feste Muster. Korrekt geklammerte Terme: kontextfrei, nicht regulär — man muss die Schachtelung zählen. Datumsangaben TT.MM.JJJJ: regulär, es gibt sogar nur endlich viele. Vollständige Pascal-Programme: Die Syntax ist kontextfrei, dafür ist der Parser zuständig. Bedingungen wie „jede Variable ist vorher deklariert“ gehen darüber hinaus; der Compiler prüft sie in einem eigenen Schritt.

5.11Reguläre Ausdrücke in der Praxis

Diesen Abschnitt als PDF (S. 23)

Reguläre Ausdrücke stehen in keinem der beiden Lehrpläne. Sie sind hier aufgenommen, weil sie dieselbe Sprachklasse beschreiben wie Grammatik und Automat — und weil sie das einzige Werkzeug dieses Kapitels sind, das Ihnen im Alltag jede Woche begegnet.

Sie wollen in einem Chatverlauf alle Nachrichten finden, in denen eine Uhrzeit steht, egal ob 7:30 oder 18:05. Die normale Suche verlangt jede Uhrzeit einzeln. Ein regulärer Ausdruck beschreibt stattdessen das Muster einmal: [0-9]+:[0-9][0-9] — eine oder mehr Ziffern, ein Doppelpunkt, zwei Ziffern. Er benutzt nur Bausteine aus der Tabelle dieses Abschnitts.

Was in 5.5 als Grammatik und in 5.6 als Automat auftrat, schreibt man im Alltag als regulären Ausdruck. Editoren, Suchfunktionen, Formularprüfungen und Logauswertungen benutzen sie täglich.

Ausdruck Bedeutung passt auf
abb genau diese Folge abb
a* beliebig viele aa, auch keines ε, a, aaa
a+ mindestens ein aa a, aaa
a? höchstens ein aa ε, a
[a-z] ein Zeichen aus dem Bereich k
(ab)+ Wiederholung der Gruppe ab, ababab
a|b Alternative a oder b

Ein Bezeichner ist damit [A-Za-z][A-Za-z0-9]*, eine Dualzahl ohne führende Null 1[01]*, eine gerade Dualzahl 1[01]*0.

import re

muster = re.compile(r"[A-Za-z][A-Za-z0-9]*$")
for text in ["zaehler", "2fast", "x1", "mein wert"]:
    print(text, bool(muster.match(text)))

Unter der Haube übersetzt die Bibliothek den Ausdruck in einen endlichen Automaten — und läuft ihn genau so ab, wie Sie es in 5.9 programmiert haben.

Arbeitsauftrag 11
  1. Schreiben Sie reguläre Ausdrücke für: Wörter über {a,b}\{a,b\} mit aa; ungerade Dualzahlen; deutsche Postleitzahlen; eine E-Mail-Adresse in grober Näherung.
  2. Prüfen Sie mit dem Python-Beispiel Ihre Ausdrücke aus Aufgabe 44.
  3. Begründen Sie, warum sich mit regulären Ausdrücken nicht prüfen lässt, ob in einem Term gleich viele öffnende wie schließende Klammern stehen.
Lösung vergleichen
  1. gesucht regulärer Ausdruck
    Wörter über {a,b}\{a,b\} mit aa [ab]*aa[ab]*
    ungerade Dualzahlen 1|1[01]*1
    deutsche Postleitzahlen [0-9]{5}
    E-Mail-Adresse (grob) [\w.-]+@[\w.-]+\.[a-z]+

    {5} heißt „genau fünfmal“, \w steht für einen Buchstaben, eine Ziffer oder _.

  2. Damit der Ausdruck den ganzen Text erfassen muss, verwendet man fullmatch:

    import re
    
    muster = re.compile(r"[0-9]{5}")
    for text in ["66564", "01067", "6656", "123456", "D-66564"]:
        print(text, bool(muster.fullmatch(text)))

    Die ersten beiden ergeben True, die übrigen False. Mit match und ohne $ am Ende würde auch 123456 durchgehen — der Anfang passt ja.

  3. Ein regulärer Ausdruck beschreibt eine reguläre Sprache, und dazu gibt es einen endlichen Automaten. Um gleich viele öffnende wie schließende Klammern zu prüfen, müsste er sich unbeschränkt viele offene Klammern merken. Mit endlich vielen Zuständen geht das nicht — dasselbe Argument wie bei anbna^n b^n.

5.12Zusammenfassung

Diesen Abschnitt als PDF (S. 24)

Wiederholungsaufgaben

  1. Erklären Sie die vier Bestandteile einer Grammatik an einem selbst gewählten Beispiel.
  2. Geben Sie zur Sprache „alle Wörter über {0,1}\{0,1\}, die mit 0 beginnen und auf 1 enden” eine reguläre Grammatik, einen DEA und einen regulären Ausdruck an.
  3. Wandeln Sie den Automaten aus Aufgabe 48 in eine Grammatik zurück und prüfen Sie, ob Sie dieselbe Sprache erhalten.
  4. Erklären Sie einem Mitschüler in fünf Sätzen, warum ein endlicher Automat keine Klammern prüfen kann.
  5. Welche Teile eines Compilers arbeiten mit endlichen Automaten, welche mit Grammatiken? Begründen Sie.
Informatik 11/12 | Automaten und SprachenDruckfassung (PDF) Notebook (.ipynb) Unterrichtsmaterial