Übungen

Aufgabe 1:

Man kann zeigen, dass die Sprache L = {anbncn | n = 1, 2, 3, ...} nicht mit einem Kellerautomaten erkannt werden kann. Diese Sprache besteht aus Wörtern, die wie folgt aufgebaut sind:

abc, aabbcc, aaabbbccc, aaaabbbbcccc, ...

Zeige, dass diese Sprache mit einer Turingmaschine erkannt werden kann. Erweitere hierzu die Turingmaschine zur Erkennung von L = {anbn | n = 1, 2, 3, ...}.

X

Fehler melden

X

Suche