 |
|||
| HSG |
|
Unär-Subtraktion mit zwei Bändern
Eingabe: Band1: Minuend und Subtrahend getrennt durch '#', Kopf aus Anfang Minuend, Band2 ist leer
Die Maschine arbeitet in folgenden Phasen:
- Der Minuend wird auf Band 2 kopiert.
- Während der Subtrahend auf Band1 durchwandert wird, werden auf Band2 Striche gelöscht.
- Inhalt von Band2 wird nach Band1 verschoben.
Spiegeln
Bei einem Eingabewort w soll mit Hilfe einer Zweibandmaschine 'drehen' die Reihenfolge der Buchstaben gedreht werden. Dazu soll das Wort nach Band2 und zurück kopiert werden. Beim zweiten Kopieren soll die Reihenfolge geändert werden.
Teilstring
Auf Band1 und Band2 stehen zwei Wörter w1 und w2. Das Alphabet ist gleich {a,b}. Es soll geprüft werden, ob w2 in w1 enthalten ist. Wenn das der Fall ist, soll der - deterministische - Automat in einen Endzustand gehen.
Testdaten: w1=bbabbaabaab, w2=abaa; w1=aaabaa, w2=aaa; w1=aabaa, w2= aaa
Nondeterminism and the Substring
In ihrem Buch 'JFLAP, An Interactive Formal Languages and Automata Package' gibt Frau Rodger eine Lösung mit einer nichtdeterministischen Zwei-Band-Maschine an. ex9-2tape-substring.jff
