Lektion 3: Erzeugen und erkennen von Wörtern

Ableitungen von Wörtern

In den vergangenen Lektionen habt ihr gelernt, was formale Sprachen und Grammatiken sind. In dieser Lektion werdet ihr Werkzeuge kennenlernen, um die Wörter einer Grammatik zu erzeugen bzw. zu erkennen. Eine wichtige Art der Darstellung werden Bäume sein.

Was haben denn jetzt Bäume damit zu tun? Bin ich Förster oder was?

Bäume werden in der Informatik häufig verwendet, um hierarchische Datenstrukturen oder Prozesse darzustellen. Einen solchen Prozess stellt die Ableitung von Wörtern aus einer Grammatik dar.

Aufgabe 1: Ableitung und Ableitungsbäume

Lies das Fachkonzept: Ableitung, Ableitungsbaum und beantworte folgende Fragen:

Was ist eine Ableitung?
Wie wird ein Wort einer Sprache mit Hilfe eines Ableitungsbaums abgeleitet?

Aufgabe 2: Übungsaufgaben

Ableitungsbäume von EMail-Adressen

Erzeuge zu den folgenden Mailadressen je einen Ableitungsbaum (per Hand oder mit draw.io). Füge die Ableitungsbäume in euer Gruppendokument ein.

my@ke.ks
ke.ks@co.ook.ie
me-and@my-cook.ies

Versuche zu einer der angegebenen Adressen einen Ableitungsbaum zu erzeugen. Was fällt dir auf? Notiere deine Beobachtungen im Gruppendokument.

-n-u-@d.el
n@-u-.del
ride@my.horse

Wie müsste man die Grammatik verändern, damit die EMail-Adresse ride@my.horse erzeugt werden kann?

Gleitkommazahlen

Die folgende Grammatik definiert eine Sprache, mit der Gleitkommazahlen in der Programmiersprache Python erzeugt werden können. Das Startsymbol ist floatnumber.

floatnumber = pointfloat | exponentfloat.
pointfloat = ([intpart] fraction) | (intpart ".").
exponentfloat = (intpart | pointfloat) exponent.
intpart = digit {digit}.
fraction = "." digit {digit}.
exponent = ("e" | "E") ["+" | "-"] digit {digit}.
digit = "0"..."9".

Gib Ableitungsbäume (draw.io) für die folgenden Zahlen an:

3.14
.14
3.
007.007
2e2
.2e2
0e+0
0e-0

Wörter erkennen

Die passende Ableitung zu einem Wort zu finden ist bei den bisherigen Beispielen durch geschicktes Anwenden der Produktionen kein großes Problem gewesen. Wie verhält es sich aber, wenn die Anzahl der Produktionen steigt oder die Aufgabe der Spracherkennung von einem Computer bewältigt werden soll? Eine Möglichkeit wäre es, alle möglichen Kombinationen aus Produktionen auszuprobieren, bis eine passende Kombination gefunden ist, Brute-Force also.

Moment, das würde bei einer halbwegs komplizierten Sprache und einem etwas längeren Wort mindestens… drölfzig Möglichkeiten geben oder?

Richtig, das systematische Durchprobieren aller Möglichkeiten funktioniert lediglich bei sehr einfachen Sprachen und kurzen Wörtern in einer annehmbaren Zeit. Komplexere Grammatiken und längere Wörter erfordern Rechenzeiten bei denen einem schwindelig wird. Wie kann Spracherkennung also effizienter gestaltet werden?

Die Antwort auf diese Frage sind zustandbasierte Systeme, diese werden in der Informatik häufig verwendet. Bei den hier verwendeten Systemen handelt es sich um Automaten. In der kommenden Lektion werdet ihr diese noch genauer kennenlernen. Wir starten hier direkt mit der Anwendung dieser Systeme. Dafür betrachten wir ein verweinfachtes Beispiel der Gleitkommazahlen von oben.¹⁾

kommazahl = intpart "." intpart.
intpart = digit {digit}.
digit = "0" | "1" | "2".

Eine Kommazahl besteht hier also aus einer nichtleeren Folge von Ziffern, gefolgt von einem Punkt und dann wieder eine nichtleere Folge von Ziffern. Beipsiele wären folgende:

20.0
001.100
0.000

Zustandsbasierte Spracherkennung

Eine Möglichkeit die Grammatik der Kommazahlen abzubilden liefert folgender Automat. Dieser ließt die möglichen Kommazahlen zeichenweise und ändert seinen Zustand je nach eingelesener Ziffer.

Der Startzustand ist hier q0 (Kreis mit Dreieck), danach wird eine Ziffer eingelesen (Pfeil) und der Automat geht in den Zustand q1 (nächster Kreis). Die Eingabe weiterer Ziffern lässt den Automaten in Zustand q1 verbleiben. Nach Eingabe eines Punktes geht der Automat in den Zustand q2. Wird nun wieder eine Ziffer eingegeben, geht der Automat in Zustand q3 und verbleibt bei Eingabe weiterer Ziffern. Zustand q3 ist als Endzustand markiert (doppelte Kreislinie). Wenn der Automat am Ende des Einlesens in q3 ist, wurde eine gültige Kommazahl eingelesen. In folgenden Bildern kannst du dies am Beispiel der Kommazahl 20.01 nachvollziehen.

Schritt 1

Schritt 2

Schritt 3

Schritt 4

Schritt 5

Schritt 6

Zustände

Warum stellt eine Zeichenkette, die in den Zustand q4 führt, keine gültige Kommazahl dar?
Erweitert den Automaten und die Sprache so, dass sie nicht nur die Ziffern 0, 1 und 2, sondern alle Ziffern erkennt. Was ändert sich hierbei?
Erarbeitet den Ablauf des Erkennens der Eingaben 1234.56789 und 987.654.321 mit dem angepassten Automaten. Notiert euch die Reihenfolge der durchlaufenen Zustände (z.B. $q_0\to q_1\to q_1 \ldots$). Welche Eingaben werden akzeptiert?

Einen genaueren Einblick in die wunderbare Welt der Automaten erhaltet ihr in der kommenden Lektion.

¹⁾

Struktur des Inhalts und das folgende Beispiel stammen von: https://www.inf-schule.de/sprachen/sprachenundautomaten/spracherkennung/endlicherautomat/fallstudie_zahlen/zustandsbasiertessystem (31.08.2020)