Übungen zur TM als Akzeptor

1. Analysieren Sie die gegebenen Turingmaschinen A, B, C, D, E und F (die Links führen zu den Automaten in FLACI, Dateien für AutoEdit gibt es hier unten). Ermitteln Sie jeweils das Eingabealphabet, die End- und -Zustandsmenge. Prüfen Sie, ob folgende Wörter von der TM erkannt werden:

• • w1 = 101
  • w2 = 0111
  • w3 = 11000
  • w4 = 11
  • w5 = 0011
  • w6 = 00111111

Ermitteln Sie jeweils die Sprache L(TM).

2. Die Turingmaschine in der Datei Palindrom.xml (Link FLACI) prüft, ob die Eingabe ein Palindrom ist. Analysieren Sie die Arbeitsweise der Turingmaschine. nur im LK: Vergleichen Sie die Prüfung mit der beim Kellerautomaten.

Hinweis: Die XML-Dateien funktionieren in Autoedit und lassen sich in FLACI importieren.