Spracherkennung mit endlichen Automaten
Problem: Erkennen von Kommazahlen
In einem Python-Programm können Zahlen auftreten, die ein Komma enthalten.
Python verwendet jedoch einen Punkt als Dezimaltrennzeichen (anstelle des Kommas).
Gültige Kommazahlen in Python sind z.B. 1.0, 3.14 oder -2.71828.
Wenn ein Python-Programm gestartet wird, prüft das Python-Ausführungssystem (Interpreter), ob das Programm syntaktische Fehler enthält.
Dabei wird auch überprüft, ob die Kommazahlen korrekt geschrieben sind.
Beispielsweise würde die Zuweisung x = 3.1.4 einen Fehler verursachen, da in einer Kommazahl nur ein einziger Punkt erlaubt ist.
Das Python-Ausführungssystem muss also erkennen können, ob eine Zeichenkette in einem Programm zu der Sprache der Kommazahlen gehört.
In diesem Abschnitt betrachten wir vereinfachte Kommazahlen, die nur die Ziffern 0, 1, 2 enthalten und immer positv sind. Die Sprache dieser vereinfachten Kommazahlen wird durch folgende Syntaxdiagramme beschrieben:
Kommazahl:
Ganzzahlteil:
Ziffer:
Erkennen von Kommazahlen mit einem endlichen Automaten
Um zu erkennen, ob eine Zeichenkette zu einer Sprache gehört, verwendet man oft endliche Automaten. Der folgende endliche Automat prüft, ob eine Zeichenkette zu der Sprache der vereinfachten Kommazahlen gehört:
Aufgabe 1
Gib in der obenstehenden Simulator das Wort 121.011 ein (Eingabefeld unten in der Mitte).
Starte die Simulation durch einen Klick auf den Pfeil (Button unten links).
Verwende den Button "vor" um zu beobachten, wie der Automat die Eingabe abarbeitet.
- Jedes Kästchen im endlichen Automat steht für einen Zustand. Der endliche Automat befindet sich immer in einem Zustand. Dies ist der Zustand, der rot hervorgehoben ist. Beschreibe, wie der Automat entscheidet, in welchen Zustand er als nächstes übergeht.
- Beschreibe, wann der Automat seine Arbeit beendet und ein Ergebnis liefert.
Aufgabe 2
Im obenstehenden Automaten besitzt Zustand Z3 einen doppelten Rahmen.
Ein Zustand mit einem doppelten Rahmen wird Endzustand oder akzeptierender Zustand genannt.
Liest ein Automat ein Wort vollständig ein und befindet sich anschließend in einem Endzustand (=akzeptierenden Zustand),
so gehört das Wort zu der Sprache des Automaten. Man sagt auch: Der Automat akzeptiert das Wort.
Liest ein Automat ein Wort vollständig ein und befindet sich anschließend nicht in einem Endzustand,
so gehört das Wort nicht zu der Sprache des Automaten. Man sagt auch: Der Automat akzeptiert das Wort nicht.
- Begründe: Der obenstehende Automat akzeptiert jede vereinfachte Kommazahl.
- Begründe: Der obenstehende Automat akzeptiert jede Zeichenkette, die keine vereinfachte Kommazahl ist, nicht.
Aufgabe 3
- .2 (steht für 0.2)
- 21. (steht für 21.0)
Entwickle eine endliche Automaten, der neben den vereinfachten Kommazahlen auch Zahlen Kommazahlen akzeptiert, bei denen entweder vor oder nach dem Punkt nichts steht.
Tipps:
- Ein Automat kann auch mehrere Endzustände haben.
- Orientiere dich an dem Automaten aus dem vorherigen Simulator.
Aufgabe 4
Hinweis: Um Verwechselungen zu vermeiden, wird in dieser Aufgabe anstelle des Leerzeichens das Gleichheitszeichen
= verwendet.Tipp: Lege zunächst ein geeignetes Alphabet fest. Verwende dazu den Button abc in der oberen Menuleiste.
Turtleanweisung:
WS:
Zahl:
Ziffer:
