Theoretische Informatik

Projektbeschreibung

Formale Sprachen bilden die Grundlage der theoretischen Informatik und haben innerhalb der Informatik ein breites Anwendungsspektrum. Den Teilnehmern sollten die Grundzüge der Theorie formaler Sprachen aus der entsprechenden Vorlesung bekannt sein. Besondere Aufmerksamkeit wurde dort den kontextfreien und den regulären Sprachen geschenkt. Reguläre Sprachen haben eine vergleichsweise kleine Ausdrucksstärke, sind jedoch sehr gut handhabbar. Probleme reguläre Sprachen betreffend sind entscheidbar, außerdem haben sie gute Abschlusseigenschaften und es gibt es viele Beschreibungsmöglichkeiten, wie endliche Automaten, Grammatiken, reguläre Ausdrücke, endliche Monoide etc.

In diesem Programmierprojekt soll nun eine Software zur Verarbeitung und Visualisierung formaler Sprachen erstellt werden, wobei der Fokus auf den regulären Sprachen liegen soll.

Ziele

Die Verarbeitung betrifft das Eingeben und Speichern von Sprachbeschreibungen (z.B. als Automat), das Uberführen von einer Beschreibung in eine andere (z.B. Automat hin zu regulärem Ausdruck), sowie das Anwenden elementarer Operationen, wie das Schneiden zweier Sprachen.

Für die verschiedenen Beschreibungsarten sollen geeignete Visualisierungen gefunden werden. Ebenso wünschenswert wäre das Darstellen verschiedener Vorgänge und Algorithmen, wie z.B. das Erkennen eines Wortes in einem Automaten oder das Minimieren eines deterministischen Automaten.

Die modulare Natur der Aufgabenstellung erlaubt es den Umfang des Projekts an den Bearbeitungszeitraum anzupassen. Das Endprodukt könnte Verwendung in der Lehre finden, z.B. im Rahmen der Veranstaltung Theoretische Informatik. Hinreichende Funktionalität und Qualität vorausgesetzt ist ebenso ein forschungsbezogener Einsatz denkbar.

Inhalte

Bei der Bearbeitung der Aufgabe wird man sich mit folgenden Inhalten auseinandersetzen:

  • Implementierung grundlegender formalsprachlicher Konzepte, Algorithmen
  • GUI und Visualisierung
  • Datenhaltung
  • Modulare und skalierbare Softwarearchitektur

Technische Grundlagen

Als Programmiersprache schlagen wir Java vor. Weitere Werkzeuge kqnnen sein: Swing, XML, sowie weitere Bibliotheken, etwa zum Graphenzeichnen oder zur Datenhaltung und Verarbeitung.