Folge 26 - Einfachste Sprachen

1. Einführende Beispiele

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. Auch höhere Computersprachen wie Pascal, Java und C++ sind noch recht kompliziert, wenngleich sie schon sehr viel einfacher sind als als die deutsche Umgangssprache.

Wir wollen uns im Folgenden mit noch einfacheren Sprachen befassen, und zwar mit den einfachsten Sprachen, die es überhaupt gibt, nämlich mit den regulären Ausdrücken.

2. Reguläre Ausdrücke

Ein gutes Beispiel für einen regulären Ausdruck stellen die Bezeichner der meisten Programmiersprachen dar, welche immer nach eindeutigen Regeln gebildet werden, wie z.B. in der Sprache Pascal:

  1. Das erste Zeichen muss ein Buchstabe sein
  2. Die folgenden Zeichen können Buchstaben oder Ziffern sein.

Diese beiden Regeln erlauben es einem Pascal-Compiler auch, festzustellen, ob ein mutmaßlicher Bezeichner lexikalisch korrekt ist:

Beispiel 1: Umfang

Der Bezeichner fängt mit einem Buchstaben an. Damit ist der Regel 1 Genüge getan. Alle folgenden Zeichen sind ebenfalls Buchstaben. Damit ist die Regel 2 erfüllt. Der Bezeichner "Umfang" ist lexikalisch korrket.

Beispiel 2: Tea4Two

Auch dieser Bezeichner ist lexikalisch korrekt. Das erste Zeichen ist ein Buchstabe (Regel 1), alle anderen Zeichen sind entweder Buchstaben oder Zahlen (Regel 2).

Beispiel 3: 4You

Das erste Zeichen ist kein Buchstabe, sondern eine Ziffer. Damit ist Regel 1 verletzt. Der Compiler meldet jetzt einen lexikalischen Fehler, wahrscheinlich "ungültiger Bezeichner" oder so etwas in der Art.

Beispiel 4: Tea 4 Two

Das erste Zeichen ist ein Buchstabe, Regel 1 ist somit erfüllt. Das zweite und das dritte Zeichen sind ebenfalls Buchstaben, noch ist die Regel 2 also erfüllt. Das vierte Zeichen ist ein Leerzeichen. Bezeichner dürfen laut Regel 2 aber nur Buchstaben oder Ziffern enthalten. Regel 2 wurde also verletzt.

Beispiel 5: fysique

Obwohl das Wort "Physik" ganz anders geschrieben wird, erkennt der Compiler keinen lexikalischen Fehler, das eigenartige Wort würde also als korrekter Bezeichner durchgehen.

3. Graphische Darstellung von regulären Ausdrücken / Übergangsfunktionen

Beispiel 1

Betrachten Sie jetzt folgende Abbildung:

Was Sie hier sehen, ist die graphische Darstellung der beiden Regeln zur Bildung von Pascal-Bezeichnern:

  1. Das erste Zeichen muss ein Buchstabe sein
  2. Die folgenden Zeichen können Buchstaben oder Ziffern sein.

Die Graphik ist nichts anderes als die graphische Darstellung der Übergangsfunktion eines determinierten endlichen Automaten, womit wir endlich beim Hauptthema dieser Folge wären (hat aber auch lange gedauert).

Ein solcher determinierter endlicher Automat, häufig als DEA abgekürzt, hat bestimmte Zustände. Unser DEA für Bezeichner hat genau zwei Zustände (daher ist der Automat auch endlich). Die beiden Zustände werden hier mit Ziffern bezeichnet. Der DEA startet immer mit dem Startzustand, der meistens die Ziffer 1 oder 0 trägt.

Der DEA kann nun unter bestimmten Bedingungen seinen Zustand ändern. Wenn sich unser Automat im Startzustand befindet und dann einen Buchstaben erkennt, also ein Zeichen aus der Menge {a..z, A..Z}, so geht er in den Zustand 2 über. Dieser Übergang wird durch den ersten Pfeil in der Abbildung angedeutet. Das Ende des Pfeils zeigt auf den neuen Zustand, und an den Pfeil schreibt man die Zeichen, die den Automaten in diesen neuen Zustand überführen.

Wenn sich unser DEA nun in dem Zustand 2 befindet, so gibt es keine Möglichkeit, zurück in den Zustand 1 zu gelangen; die Übergangsfunktion (bzw. ihre graphische Darstellung) enthält keinen Pfeil von 2 nach 1. Es gibt auch keinen Zustand 3, in den der Automat gelangen könnte. "Sieht" der Automat im Zustand 2 einen Buchstaben, so führt das dazu, dass er im Zustand 2 verbleibt. Und "sieht" der Automat eine Ziffer, also ein Zeichen aus der Menge {0..9}, so verbleibt er ebenfalls im Zustand 2. Das gilt allerdings nur, wenn er sich bereits im Zustand 2 befindet. Erkennt der Automat eine Ziffer, wenn er sich im Zustand 1 befindet, so geht er in einen Fehlerzustand über, der üblicherweise nicht mit in die Übergangsfunktion eingezeichnet wird. Auch wenn der Automat ein anderes Zeichen erkennt, z.B. das Zeichen "%" oder einen Punkt, geht er in den Fehlerzustand über.

Beispiel 2

Betrachten wir ein zweites Beispiel:

Dieser Automat besitzt drei Zustände. Er startet wieder im Startzustand 1. Erkennt er als in diesem Zustand eine Ziffer, so gelangt er in den Zustand 3, erkennt er dagegen ein Plus- oder Minus-Symbol, so gelangt er in den Zustand 2. Durch alle anderen Zeichen kommt der DEA in den Fehlerzustand, der hier wieder nicht eingezeichnet wurde. Aus dem Zustand 2 kommt der DEA durch eine Ziffer in den Zustand 3, ansonsten in den Fehlerzustand. Wird im Zustand 3 eine Ziffer erkannt, so bleibt der DEA im Zustand 3, durch andere Zeichen gelangt er wieder in den Fehlerzustand.

Es ist unschwer zu erkennen, was die in der Zeichnung dargestellte Übergangsfunktion eigentlich überprüft: Ist eine Zeichenkette eine gültige int-Zahl?

Angenommen, es soll überprüft werden, ob die Zeichenkette "+5.57" eine korrekte int-Zahl ist. Der DEA beginnt im Startzustand 1 und erkennt als erstes das Plus-Zeichen. Also wird der Zustand 2 eingenommen. Nun wird die Ziffer "5" erkannt. Der DEA befindet sich jetzt im Zustand 3. Dieser Zustand ist ein Endzustand.

Endzustand heißt nicht, dass der Automat nun am Ende ist; es können durchaus noch weitere Zeichen kommen. Wenn aber das letzte Zeichen analysiert worden ist, wenn der zu untersuchende String sein Ende erreicht hat, dann sollte sich der DEA gefälligst in einem Endzustand befinden und nicht in einem der anderen Zustände.

Die Zeichenkette "+5" wäre demnach eine korrekte int-Zahl, da sich der DEA nach Abarbeitung von "+5" in dem Endzustand 3 befindet. Jetzt kommt aber dummerweise noch das Zeichen ".", welches für den Zustand 3 nicht vorgesehen ist. Der DEA gerät in den Fehlerzustand. Einmal im Fehlerzustand; immer im Fehlerzustand. Es ist jetzt klar, dass die Zeichenkette "+5." keine korrekte int-Zahl ist.

4. Formale Beschreibung eines DEAs

Determinierter Endlicher Automat (DEA)

Ein determinierter endlicher Automat (DEA) ist ein 5-Tupel A = (Q, S, d ,q0, F) mit

  • Q = endliche Menge von Zuständen
  • S = Eingabealphabet
  • d = Übergangsfunktion
  • q0 = Startzustand
  • F = endliche Menge von Endzuständen.

Diese Beschreibung hört sich auf den ersten Blick sehr abstrakt an, war daran liegen könnte, dass sie tatsächlich sehr abstrakt ist. Aber Sie sind von mir nach allen Regeln der didaktischen Kunst seelisch auf diese Definition vorbereitet worden. Betrachten Sie sich noch einmal die letzte Abbildung:

Die Abbildung stellt einen Determinierten Endlichen Automaten (DEA) graphisch dar. Wir wollen jetzt diesen Automaten gründlich analysieren.

Endliche Menge von Zuständen Q

Man erkennt drei Zustände, also kann man schreiben: Q = {1, 2, 3}.

Eingabealphabet S

Das Eingabealphabet dieses DEAs besteht aus sämtlichen Zeichen, die an irgendeinem der Pfeile auftauchen. Also gilt hier: S = {+, -, 0, 1, ..., 9}. Mit anderen Worten: Das Eingabealphabet S dieses DEAs besteht aus den Ziffern von 0 bis 9 sowie dem Plus- und dem Minuszeichen.

Übergangsfunktion d

Die Übergangsfunktion d (delta, falls Ihr Browser das griechische Zeichen nicht korrekt darstellt) definiert genau, was passiert, wenn sich der DEA in dem Zustand z befindet und gerade das Zeichen c verarbeitet. Befindet sich der DEA z.B. im Zustand 2 und verarbeitet das Zeichen "5", so gelangt er in den Zustand 3. Die Übergangsfunktion kann graphisch dargestellt werden so wie in den Zeichnungen oben, oder in Form einer Tabelle:

alter
Zustand qn
Zeichen s neuer
Zustand qn+1
1 + 2
1 - 2
1 0, 1, 2, ... 9 3
2 0, 1, 2, ... 9 3
3 0, 1, 2, ... 9 3
Startzustand q0

Ein jeder DEA muss genau einen Startzustand haben. In unserem DEA ist der Zustand mit der Ziffer 1 der Startzustand.

Endliche Menge von Endzuständen F

Ein DEA muss mindestens einen Endzustand besitzen, er kann aber auch mehrere solcher Endzustände haben. In unserem Fall hat der DEA nur einen Endzustand, nämlich den Zustand 3.

Zum Begriff "Determinierter Endlicher Automat"

Die Klasse von Automaten, die eben vorgestellt wurde, wird als "determiniert" und "endlich" bezeichnet. Das "endlich" bezieht sich auf die endliche Zahl von Zuständen. Das "determiniert" heißt, dass die Übergangsfunktion eindeutig ist. Sei qn irgendein Zustand aus Q und s irgendein Zeichen aus S, so ist genau festgelegt, welches der Folgezustand qn+1 ist.

Übung 26.1 ( 7 Punkte)

Zeichnen Sie die Übergangsfunktion eines DEA, der ganze und reelle Zahlen mit oder ohne Vorzeichen wie zum Beispiel "+12", "+12.5", -"3.6578" oder "7" erkennt (2 Punkte).

Geben Sie die Zustände, das Eingabealphabet und die Endzustände in Form von Mengen an (1 Punkt). Stellen Sie die Übergangsfunktion in Form einer Tabelle dar (1 Punkt). Zeigen Sie (durch Angabe der Zustände), dass die Zeichenkette "-12.57" den Automaten in einen Endzustand überführt (1 Punkt).

Erweitern Sie den DEA so, dass auch reelle Zahlen mit ganzzahligen Exponenten erkannt werden können, z.B. "-45.20E-2" oder "14.6E120" oder "6.22E23" (2 Punkte).

Übung 26.2 (3 Punkte)

Zeichnen Sie die Übergangsfunktion eines DEA, der alle Zeichenketten erkennt, die

a) ausschließlich aus Ziffern (0..9) bestehen und

b) mit der Ziffernfolge "007" abschließen.

Die Zeichenkette "15482007" wäre also korrekt, die Zeichenfolge "165007342" dagegen nicht.

Übung 26.3 (2 Punkte oder mehr)

Zeichnen Sie die Übergangsfunktion eines DEA, der die römischen Zahlen von I bis XIX erkennt. Je weniger Zustände Ihr DEA, desto mehr Punkte bekommen Sie, und zwar 12 - Z (Zahl der Zustände).

Zur Erinnerung - die römischen Zahlen von 1 bis 19 sind:

I, II, III, IV, V, VI, VII, VIII, IX, X, XI, XII, XIII, XIV, XV, XVI, XVII, XVIII, XIX.

5. Sprache L eines DEAs

Für ein Alphabet S bezeichnen wir mit S* die Menge aller endlichen Symbolfolgen über S, das ist die Menge aller Worte über dem Alphabet S einschließlich des leeren Wortes e.

Wendet man die Übergangsfunktion des Automaten für reelle Zahlen (Abb. 3) auf die Zeichenfolge +12.5 an, so "landet" der Automat im Zustand 5. Dies ist einer der beiden Endzustände. Wird die Übergangsfunktion dagegen auf die Symbolfolge +12. angewandt, so hält der Automat im Zustand 4, der nicht zu den Endzuständen gehört.

Sprache L eines DEAs

Die von einem endlichen Automaten A akzeptierte Menge von Worten L(A) ist :

L(A) = {w aus S*| d (q0,w) aus F }

L(A) heißt auch die Sprache von A.

Diese Definition ist für angehende Informatiker im 3. oder 4. Semester gedacht, daher kann an dieser Stelle eine "Übersetzung" nicht schaden. Also, los geht's, und zwar in kleinen Schritten, die eigentlich jede(r) verstehen müsste.

Eingabealphabet S

S ist ja bekanntlich das Eingabealphabet des Automaten. Denken Sie an den Automaten für int-Zahlen, dort bestand das Eingabealphabet S aus der Menge {+, -, 0..9}. Das Eingabealphabet für den Automaten "Pascal-Bezeichner" bestand aus der Menge {a..z, A...Z, 0..9}, war also um Einiges größer.

Zeichenkette S*

Unter einer Zeichenkette versteht man die Menge aller möglichen Kombinationen von Zeichen aus dem Eingabealphabet. Wenn wir uns wieder den DEA für int-Zahlen anschauen, so wäre "+5+6+7+8" eine solche Zeichenkette aus dem Eingabealphabet. Auch "+57" wäre eine solche Zeichenkette, und natürlich auch "+++++". Sie sehen sofort: Es gibt sinnvolle und auch sinnlose Zeichenketten, die aus dem Eingabealphabet gebildet werden können.

Wort

Dieser Begriff steht für eine "sinnvolle Zeichenkette". Die Definition, die so schwer zu verstehen ist, gibt nun genau an, welche der vielen möglichen Zeichenketten sinnvolle Worte sind, und welche Zeichenketten eben nur sinnlose Zeichenketten sind. Sinnvolle Worte sind nur solche Zeichenketten, die den Automaten vom Startzustand q0 in einen der Endzustände aus F überführen.

Sprache

Die Menge aller Worte eines DEAs wird auch als "Sprache des DEAs" bezeichnet. Wenn der DEA mit dem Symbol A (für Automat) bezeichnet wird, dann ist L(A) die Sprache dieses Automaten (L ist die Abkürzung für language, engl. für Sprache).

Übung 26.4 (8 Punkte)

Hier sehen Sie einige korrekte Java-Methoden-Köpfe:

public void gibInhalt();

public int gibVolumen();

public double gibUmfang(int radius);

private void setzeKoordinaten(int x, int y);

private void setzeFarbe(String neueFarbe);

public void totalerBloedsinn(int x, double y, String s, boolean b);

Entwickeln Sie einen DEA (Eingabealphabet, Übergangsfunktion etc.), der in der Lage ist, korrekte Java-Methoden-Köpfe zu erkennen.

Tipp: Das Eingabealphabet S muss nicht stets aus einfachen Zeichen wie "0..9" oder "A..Z" bestehen, sondern kann bei Bedarf auch komplexere Zeichen oder Symbole enthalten, z.B. Schlüsselworte wie "public" oder "private" sowie "void" oder "int". Auch bereits durch andere DEAs definierte Begriffe wie "bezeichner" oder "real-Zahl" können Sie als Symbol für das Eingabealphabet verwenden. Das wird Ihnen sicherlich einige Zustände in Ihrem Automaten einsparen.

6. Nichtdeterminierte Endliche Automaten (NDEAs)

Dieser Abschnitt ist nur für die Klausur- / Abiturleute relevant; er wurde daher auf eine eigene Theorieseite ausgelagert. Es gibt keine "Punkte" für diese Theorieseite, dennoch ist es für die Klausurleute unerlässlich, dass sie diese Seite gründlich durcharbeiten. In der nächsten Klausur kommt garantiert eine Aufgabe oder zumindest eine Teilaufgabe zum Thema DEAs und NDEAs dran, weil die neuen Abiturbestimmungen für das Zentralabitur Informatik in NRW ganz direkt dieses Thema vorsehen.

weiter mit Folge 27: Lexikalische Analyse

Im Mittelpunkt dieser Folge steht die Frage, wie man Determinierte Endliche Automaten dazu einsetzen kann, einen Java-Befehl, der aus mehreren Variablen, Zahlen und Operatoren besteht, lexikalisch zu analysieren.

Diese HTML-Seite wurde erstellt von Ulrich Helmich am 25. Juli 2006 und nur leicht verändert am 17. Juni 2008. Eine weitere Überarbeitung ist nicht geplant. Ich arbeite zur Zeit an der PDF-Version dieser Folge, die schönere Graphiken sowie ein zusätzliches größeres Beispiel für einen DEA enthält, nämlich Pascal-Prozedurköpfe.






IMPRESSUM