Suche Home Einstellungen Anmelden Hilfe  

4.2.3 LBA und kontextsensitive Grammatiken

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

Benutzer: Gast • Besitzer: senn • Zuletzt gešndert am: