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>abc</aa>, <ab>abc</abb>, ... 

Man kann zeigen, dass die Sprache LMyXML nicht mit Hilfe eines Kellerautomaten erkannt werden kann. Zur Sprachanlyse benötigt man ein mächtigeres Verarbeitungsmodell:

Turingmaschine

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.

X

Fehler melden

X

Suche