Eine Turingmaschine heißt linear beschränkt (LBA), wenn alle von ihr erreichbaren Konfigurationen αzβ die Bedingung |α∙β|≤n erfüllen.
Satz: Zu jeder Chomsky-1-Grammatik G= ⟨Φ,Σ,R,S⟩ gibt es eine nichtdeterministische LBA M= ⟨Φ‘,Σ‘,#,δ,S‘,F⟩, die L(G) akzeptiert und umgekehrt.
Beweisidee: (G→M) Sei G= ⟨Φ,Σ,R,S⟩ gegeben. Die zu konstruierende Maschine M mit Φ ∪Σ als Bandalphabet bekommt x= a0…an als Eingabe. Wir wählen nichtdeterministisch eine Regel u→v∈R und wenden sie auf das erste Vorkommen von v in x an. Dabei kann das Eingabewort nicht länger werden. Der Automat setzt dies fort, bis das Band nur noch #S# enthält.
(M→G) Konfigurationsübergänge der Maschine lassen sich auf Symbole der Grammatik abbilden (Schöning, S. 86).
Anmerkung: Hier ist wichtig, dass M nichtdeterministisch ist. Zwar können auch deterministische TMen Chomsky-1-Sprachen akzeptieren, ob sie dann aber noch linear beschränkt sind, ist offen (LBA-Problem).
Satz: Chomsky-0-Sprachen werden genau durch allgemeine Turingmaschinen akzeptiert
Chomsky-1 unterscheidet sich nur durch die Längenmonotonie von Chomsky-0, und der einzige Punkt, an dem die Längenmonotonie im “Beweis” oben relevant war, war die lineare Beschränktheit.
Chomsky-1-Sprachen sind abgeschlossen unter Schnitt, Vereinigung, Komplement (anders als Chomsky-2!), Verkettung und Sternbildung.
Diese Eigenschaften lassen sich durch geeignete Verschaltung von Turingmaschinen zeigen. Problematisch dabei ist allenfalls die lineare Beschränkung.
Interessant ist vor allem die Komplementbildung. Die Idee dabei ist, dass man eine Turingmaschine bauen kann, die alle Wörter erzeugt, die nicht länger als ein zu untersuchendes sind und die dann abklappert. Man kann zeigen, dass das mit einem linear beschränkten Band geht. Die Aufzählung geht für allgemeine Regelsprachen nicht mehr, deshalb:
Chomsky-0-Sprachen unter Komplementbildung nicht abgeschlossen. Dieser Umstand hat recht profunde Konsequenzen. Hätte man z.B. eine Sprache aller “wahren” Aussagen innerhalb eines formalen Systems irgendeiner Art und wäre sie eine allgemeine Regelsprache, so wäre das Komplement möglicherweise keine allgemeine Regelsprache mehr – da wir aber für noch allgemeinere Sprachen das Wortproblem nicht mehr lösen können, würde das bedeuten, dass wir zwar garantiert ausrechnen können, dass eine Aussage wahr ist, aber möglicherweise nicht, dass sie falsch ist.