Tojio Lab

Das Formal Language Tool (benötigt Java WebStart) bietet eine Benutzeroberfläche zum visuellen Erstellen endlicher Automaten für reguläre Sprachen.
Was bedeutet das? Wenn wir etwa auf einem Mobiltelefon eine SMS verfassen und das Gerät versucht, das angefangene Wort zu vervollständigen, kommt ein sog. endlicher Automat (manchmal auch ‘Netzwerk’ genannt) zum Einsatz. Angenommen, wir haben ein ‘M’ eingetippt, dann gibt es zu diesem Zeitpunkt im Netzwerk unten folgende Möglichkeiten, wie das Wort weitergehen kann: [M]ontag(e), [M]ontur, [M]oment, [M]ama, [M]artin:

Je weiter die Eingabe vervollständigt wird, desto weniger Möglichkeiten bleiben natürlich offen: nach der Eingabe ‘Mo’ wären die möglichen Wörter, die automatisch vervollständigt werden können: [Mo]ntag(e), [Mo]ntur und [Mo]ment:

Die Kreise mit den doppelten Linien sind so genannte ‘Endzustände’ – in unserem Fall repräsentieren sie und die Wege zu ihnen diejenigen Wörter, die das Mobiltelefon bei der Eingabe von selbst komplettieren kann.

Das Prinzip endlicher Automaten stellt eine sehr effiziente Möglichkeit dar, Aufgaben wie die oben beschriebene zu erledigen. Über die Komplettierung von Wörtern (das Erzeugen einer Sprache) hinaus können solche Automaten auch in der anderen Richtung benutzt werden: sie können Sprachen erkennen bzw. entscheiden, ob eine Eingabe korrekt ist.

Der folgende Automat beispielsweise prüft einfache Formeln der Aussagenlogik. Als korrekt akzeptiert er dabei [a UND b], [NICHT c] sowie [b ODER c]

Sie können hier das Formal Language Tool als Java WebStart Application starten…