Theoretische Informatik - Aufgaben

Linear beschränkte Turingmaschine

 aufwärts

Aufgabe:  

Gegeben ist die Sprache

L  =  { wwRw  |  w Element {a, b}* }

Hierbei ist wR das gespiegelte (d.h. rückwärts gelesene) Wort w.

 

  1. Beschreiben Sie informell, wie eine linear beschränkte Turing­maschine die Sprache L erkennt.
  2. Erstellen Sie mit dem Turing­maschinen-Simulator eine linear beschränkte Turing­maschine, die L erkennt. Testen Sie Ihre Turing­maschine mit dem Eingabewort abbaab.

 

 

 

up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   Datenschutz   ©   Created: 11.12.2009   Updated: 10.06.2018
Valid HTML 4.01 Transitional