TM und unbeschränkte Grammatiken bilden die gleiche Sprachklasse ab.
Jede Sprache für die überhaupt eine Grammatik gefunden werden kann, ist auch durch eine TM darstellbar und umgekehrt.
Eine Grammatik lässt sich einfach durch eine TM simulieren.
Das Arbeitsband lässt sich als Bereich verstehen, auf dem ausgehend vom Eingabewort alle Satzformen hin zum Startsymbol generiert werden.
Eine TM akzeptiert ein Wort, wenn das Startsymbol erreicht wird.
Es werden Schritt für Schritt die als Übergänge kodierten Regeln an passenden Stellen in der Eingabe anwendet.
Eine Regel entspricht mehreren Übergängen, da oft Hilfsbewegungen zum Verschieben von Symbolen auf dem Arbeitsband nötig sind.
Die Auswahl der Regeln ist nichtdeterministisch.
Um umgekehrt zu zeigen, dass jede von einer TM akzeptierte Sprache auch von einer unbeschränkten Grammatik abgeleitet werden kann,
ist eine Reduktion der 7 Komponenten auf 4 nötig.
Die Manipulationen des Arbeitsbandes der TM werden in der Grammatik ähnlich der Konfigurationsdarstellung einer TM simuliert.
D.h. anfänglich wird eine Konstellation q0 Bandsymbole Blanks erzeugt, wobei die Bandsymbole dem Eingabewort entsprechen und
die Blanks weitere Arbeitsbandzellen reservieren.
Die Bandsymbole werden durch zweiteilige Symbole dargestellt.
Die erste Komponente nimmt ein Symbol des Terminalalphabets ein.
Dieser Teil des Nichtterminals wird nie verändert.
In dem zweiten Teil finden die Veränderungen statt, die durch die Manipulation der TM auf dem Arbeitsband stattfinden.
Die komplexen Symbole werden erst aus der Ableitung entfernt, wenn die TM einen Endzustand erreicht hätte.
| 
Übersicht: Sprachklassen
