Basismodul Computerlinguistik

Übung

Abschlussprojekt

Abgabe bis einschließlich 26.01.2022 in der unter Abschnitt 2 angegebenden Form an e.nie@campus.lmu.de

1. Aufgabenstellung

In diesem Projekt wird der Daciuk-Algorithmus zur Konstruktion eines Minimalen Lexikonautomaten mit verschiedenen Erweiterungen implementiert.

1.1 Organisatorische und technische Hinweise

Die Aufgabe kann höchstens zu zweit bearbeitet werden.

Akzeptiert werden Programme, die unter Python 3.8 lauffähig sind. Das bedeutet für die Python3-Version, mit der entwickelt wird: Version <= 3.8

Es darf die komplette Built-In Library verwendet werden, jedoch mit Ausnahme von graphviz keine externen (third-party) Libraries.

Bei Unklarheiten oder sonstigen Fragen zur Aufgabenstellung - fragen!

1.2 Bestehen

Die Aufgabe gilt als bestanden, wenn:

• die Basisanforderung (Abschnitt 1.3) erfüllt ist. (CL Nebenfach)
• die Basisanforderung (Abschnitt 1.3) erfüllt ist, und mindestens 3 der 5 Erweiterungen (Abschnitt 1.4) erfolgreich implementiert sind. (CL Hauptfach) Die Abgabeform ist in Abschnitt 2 angegeben.

1.3 Basisanforderung

• Implementiere den Daciuk-Algorithmus zum Erstellen eines Minimalen Lexikonautomaten wie in der vorlesung besprochen und in der Hausaufgabe 5 bereits gefordert war.
• Schreibe ein Programm, das aus einer Datei eine Wortliste einliest und daraus einen Lexikonautomaten erstellt. Zusätzlich soll das Programm dem Nutzer über die Kommandozeile die Eingabe von Wörtern ermöglichen und dann ausgeben, ob das Wort Teil der Sprache des Automaten ist. Das Programm soll sich regulär beenden, wenn der Nutzer das leere Wort, d.h. den leeren String eingibt.

1.4 Erweiterungen

Folgende Erweiterungen für das Basisprogramm sind möglich. Es sollen mindestens 3 von 5 Erweiterungen umgesetzt werden.

• Sprache des Automaten: Erweitere das Programm so, dass der Nutzer sich die Sprache des Automaten ausgeben lassen kann. Dabei soll der Automat einmal iterativ oder rekursiv durchlaufen werden, wobei nur diejenigen Wörter generiert werden dürfen, die Teil der Sprache des Automaten sind.
• Perfect Hashing: Erweitere das Programm sp, dass der Nutzer ein Wort und eine dazugehörige Meta-Information als String eingeben kann, welche mithilfe von Perfect Hashing in einer Hash-Tabelle gespeichert wird. Auf die gleiche Weise soll der Nutzer gespeichert Meta-Informationen zu einem Wort abrufen können.
• Grafische Darstellung: Das Programm soll die Option bieten, den Automaten als Grafik (graphviz) anzuzeigen.
• Speichern und Laden: Der Automat soll in einer Datei abgespeichert und aus einer solchen Datei wieder geladen werden können. Es soll dann beim Starten des Programmes ausgewählt werden können, ob eine Datei mit einer Wortliste oder eine Datei mit einem abgespeicherten Automaten verwendet wird, um den Automaten zu konstruieren.
• Tarjan-Tabelle: Es soll eine Tarjan-Tabelle erstellt werden können, die anschließend in einer Datei gespeichert und auch wieder geladen werden kann. Damit ist auch Speichern und Laden erfüllt.

Die Perfect Hashing-Labels und die Tarjan-Tabelle können sowohl paralle zum Daciuk-Algorithmus als auch mit einem bereits erstellten Automaten berechnet / konstruiert werden.

Hinweis: Es bietet sich an, die verschiedenen Nutzereingaben über eine Art 'Hauptmenü' abzufragen, in dem der Nutzer die verschiedenen Programmfunktion aufrufen kann. Nutzereingaben können einfach über die input()-Funktion abgefragt werden. Beispiel:

Was möchtest du tun?
    (1) Wort abfragen
    (2) Automaten zeichnen
    (3) Sprache ausgeben
Bitte eine Nummer eingeben >>> _

2. Abgabeform

• Das Projekt is bis einschließlich 26.01.2022 an e.nie@campus.lmu.de abzugeben.
• Das Projekt ist in Form von einer .py-Datei oder mehrerer .py-Dateien als .zip verpackt abzugeben.
• Der Abgabe ist eine README-Datei im .txt- oder .md-Format beizufügen, in der
  • der Programmaufruf mit allen möglichen Kommandozeilenargumenten erklärt ist.
  • beschrieben ist, welche Erweiterungen implementiert worden sind.
  • gegebenfalls beschrieben ist, wie die umgesetzten Erweiterungen aufgerufen werden.
  • kurzum: dem Nutzer alle notwendigen Informationen zur Verfügung gestellt werde, um das Programm zu verwenden, ohne in den Source Code schauen zu müssen.