|
Die Argumentation folgt der Äquivalenzskizze von TM und unbeschränkten Grammatiken.
Das Arbeitsband kann als Notizblock für die Ableitung verstanden werden.
Ausgehend vom Eingabewort werden die als Übergänge kodierten Regeln so lange angewendet, bis
das Startsymbol auf dem Arbeitsband erscheint.
Man kann sich sicher sein, dass das in der Größe beschränkte Arbeitsband ausreicht,
da das Wort genau so viele Zellen belegt, wie maximal in der Ableitung des Wortes durch die Grammatik notwendig sind.
Aus der Monotoniebeschränkung für kontextsensitive Grammatiken folgt, dass
beim Zurückführen auf das Startsymbol immer kleinere bzw. gleich lange Zwischenergebnisse entstehen.
|
Übersicht: Sprachklassen
