Einstieg - Turingmaschine
MyXML
Die Sprache LMyXML soll vereinfachte XML-artige Ausdrücke beschreiben. Jedes zu L gehörende Wort soll aus einem Anfangstag, einem Text und einem Endtag bestehen. Anfangs- und Endtag sollen identisch sein. Die Tag-Bezeichner sind beliebige nicht-leere Zeichenketten, die nur aus den Buchstaben a und b bestehen. Der Text zwischen den Anfangs- und Endtag besteht nur aus den Buchstaben a, b und c.
Zur Sprache LMyXML gehören z.B.
<ab>acaa</ab>,<aa>abc</aa>,<bab>abba</bab>, ...
Nicht zur Sprache LMyXML gehören z.B.
<ab>abc<ab></ab></ab>,<ab>abc<ab>,<a>abc</b>, ...
Man kann zeigen, dass die Sprache LMyXML nicht mit Hilfe eines Kellerautomaten erkannt werden kann. Zur Sprachanalyse benötigt man ein mächtigeres Verarbeitungsmodell:
Aufgabe 1
Lade die Datei tm_myxml.jff herunter.
Öffne sie mit JFlap und teste das Verhalten des gezeigten verallgemeinerten Automaten.
Mit [Input][Step...] kannst du Eingabewörter wie z.B. <ab>acaa</ab> eingeben,
mit [Step] den Automaten dann schrittweise das Eingabewort verarbeiten lassen.
Vergleiche das neue Verarbeitungsmodell - man nennt es Turingmaschine - mit einem endlichen Automaten. Was ist
bei einer Turingmaschine anders als bei einem endlichen Automaten?
Aufgabe 2
Versuche, die Idee der heruntergeladenen Turingmaschine zur Erkennung von Wörtern der Sprache LMyXML
herauszufinden. Teste hierzu verschiedene, zur Sprache gehörende und auch nicht gehörende Wörter über dem
Alphabet {a, b, c, /, <, >}. Beschreibe die Verarbeitung in eigenen Worten.
