Die Sprache L = { aⁿbⁿ | n ∈ ℕ } mit einer Turing­maschine erkennen

Entwirf eine Turing­maschine, die Wörter der Form aⁿbⁿ akzeptiert. Achte darauf, dass die Wörter genauso viele a's wie b's enthalten.

Turing­tabelle entwerfen

Du erstellst eine ent­sprechende Turing­tabelle, indem du zuerst unten auf die Schaltfläche  Editieren  klickst und dann die Tabelle ausfüllst. Die erste Zeile steht in der Turing­tabelle schon da: Wenn die Turing­maschine im Startzustand 0 auf dem Arbeitsband ein a liest, geht sie mit dem Cursor um ein Feld nach rechts und bleibt im Zustand 0. Die Idee dabei: Im Eingabewort von innen nach außen jeweils ein a und ein zugehöriges b durch x über­schreiben.

Turing­maschine simulieren

Wenn du die Turing­tabelle fertig erstellt hast, kannst du die Turing­maschine ausprobieren. Dazu betätigst du die Schaltfläche  Simulieren  und verarbeitest das vor­geschlagene Eingabewort. Ändere das Eingabewort später einmal und überprüfe, ob Wörter, die nicht zur Sprache L gehören, zurück­gewiesen werden.

Arbeitsband

$

 

 

 

 

 

 

 

 

 

 

 

 

Eingabewort

   

 

s	a	a'	s'
0	a	R	0