Du programmierst gerne? Findest die theoretische Informatik spannend? Nun suchst du eine Bachelorarbeit, die beides vereint? Dann bist du bei uns genau richtig! Unser Ziel ist es, das Tool AutomataTutor so zu erweitern, dass Studierende parallel zur Vorlesung “Einführung in die theoretische Informatik” Aufgaben des Typs A, B und C (siehe Übungskonzeption) selbstständig üben können - und zwar wann und wo sie wollen.

Aktueller Stand

Zur Zeit umfasst das Tool hauptsächlich Aufgaben, die das Erstellen von regulären Ausdrücken oder Automaten zu gegebenen Sprachen erfordern. Bei Fehlern gibt AutomataTutor möglichst hilfreiches Feedback. Dabei versucht das Tool, zuerst natürliches Feedback zu geben. Ist dies nicht möglich, gibt es einfach Worte an, die in der Sprache vorkommen, aber nicht akzeptiert werden bzw. Worte die zwar akzeptiert werden, aber nicht zur Sprache gehören.

Implementierung

Das Frontend ist in Scala geschrieben, das Backend in C#. Der Code kann auf GitHub eingesehen werden.

Was gibt es zu tun?

• Zur Zeit ist das AutomataTutor eine Website, die nur unzureichend auf Smartphones unterstützt wird. Ein Thema ist daher die Implementierung eines Frontends/einer App für Smartphones. Die Frage, um die sich diese Arbeit dreht, ist dabei, wie man Automaten/Graphen gut auf Smartphones darstellen kann, so dass auch bei größeren Automaten (mit mehr als zehn Zuständen) ein Editieren der Zustände und Transitionen möglich und die Darstellung übersichtlich ist.
• Unterstützung weiterer Aufgaben vom Typ B / C: Prinzipiell ist hier noch alles offen außer das Erstellen von Automaten bzw. regulären Ausdrücken zu gegebenen Sprachen, Determinisieren von Automaten und Produktautomatenkonstruktion. Im Detail
  • reguläre Sprachen
    • Grammatik zu DFAs konstruieren * NFA zu Grammatiken konstruieren * epsilon-NFA in NFA übersetzen * Ausführung von Automaten zu einem Wort visualieren
    • Ardens Lemma
    • Funktionen, die reguläre Ausdrücke aufeinander abbilden (wie zum Beispiel Reversierung und Suffixe)
  • Ableitung von Grammatiken zu einem Wort prüfen
  • Turing-Maschinen * Ausführung von Turing-Maschinen visualisieren
    • Implementierung eines Tests, ob eine Turing-Maschine eine gegebene Sprache (mit einer hohen Wahrscheinlichkeit, bis zu Wörtern einer gewissen Länge, …) akzeptiert
• Das Backend effizienter gestalten. Zur Zeit kann das Tool mit komplizierteren Sprachen nur unzureichend umgehen, insbesondere beim Produzieren von Feedback.
• Automatische Aufgabengenerierung: Zur Zeit müssen Aufgaben manuell eingegeben werden, d.h. ein Instructor muss eine Aufgabe mit Aufgabentext und Automat, regulärem Ausdruck bzw. Grammatik angeben. Es ist wünschenswert, dass zu einem Aufgabentyp, wie z.B. Determinisierung, automatisch Beispielautomaten generiert werden.
• Unterstützung der Aufgabe auf Blatt 6: Um das Erstellen von Sprachen, die in formaler bzw. natürlichlich sprachlicher Formulierung vorliegen zu erleichtern, möchten wir ein Teacher-Learner-System in AutomataTutor integrieren. Dazu soll es möglich sein, Wörter anzugeben und AutomataTutor gibt als Feedback, ob das Wort in der Sprache enthalten ist oder nicht. Darüberhinaus soll es möglich sein einen regulären Ausdruck oder einen Automaten anzugeben, der die Sprache beschreibt. Falls der reguläre Ausdruck/der Automat korrekt ist, ist die Übung fertig. Ansonsten soll AutomataTutor ein Wort zurückgeben, welches in der Sprache enthalten ist, aber noch nicht vom regulären Ausdruck beschrieben wird bzw. vom regulären Ausdruck/Automaten erzeugt wird, aber nicht in der Sprache enthalten ist.

Wir haben in der Liste etwas nicht aufgeführt, was dir beim Lernen in der theoretischen Informatik geholfen hätte? Schreib uns eine Mail und wir setzen uns mit dir zusammen, um zu diskutieren, ob deine Idee in einer Bachelorarbeit umsetzbar ist!

Wir freuen uns auf dich!