Übung Basismodul Computerlinguistik

Hausaufgabe 05

18.11.21

Abgabe als .py-Datei (bei mehreren Dateien als .zip komprimiert) an e.nie@campus.lmu.de bis 02.12.2021.
Für diese Aufgabe sind 2 Wochen eingeplant.

1. Aufgabe

Implementiere den Daciuk-Algorithmus zum Erstellen eines Minimalen Lexikonautomaten nach dem CL Artikel (Seite 8-9) von Daciuk et al. Empfohlen wird auch Perez-Skript (Seite 19-20).

Das fertige Programm soll folgendermaßen aufgerufen werden:

dictionary = ["acker", "alle", "alraune", "as", "aspekt"] # Hier muss 'dictionary' eine sortierte (!) Liste von Wörtern sein.
min_dict = MinDict(dictionary)

Nützliche Vorüberlegungen:

• Wie wird die Äquivalenz zweier Zustände bestimmt?
• Wie wird das Register dargestellt?
• Sollen Zustände Objekte einer selbst-definierten Klasse sein?
• Wie findet man das "last Child" eines Zustandes?

Hinweis: Eine geeignete Datenstruktur zum Speichern der Übergänge eines Zustandes in das OrderedDict.

2. Aufgabe

Zeichne den Automaten.
Hol Dir die Funktion draw_automaton() aus Hausaufgabe 3, die einen Automaten mit graphviz zeichnet, und modifiziere sie so, dass dein Lexikonautomat gezeichnet werden kann.