Einstieg - Turingmaschine

MyXML

Die Sprache L_MyXML 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 L_MyXML gehören z.B.

<ab>acaa</ab>, <aa>abc</aa>, <bab>abba</bab>, ... 

Nicht zur Sprache L_MyXML gehören z.B.

<ab>abc<ab></ab></ab>, <ab>abc<ab>, <a>abc</b>, ... 

Man kann zeigen, dass die Sprache L_MyXML nicht mit Hilfe eines Kellerautomaten erkannt werden kann. Zur Sprachanlyse 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 L_MyXML 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.