Mit rechtslinearen Grammatiken kann allein die Reihenfolge der Wortbestandteile bestimmt werden.
In jedem Ableitungsschritt wird ein weiteres Terminal abgeleitet,
Informationen zum bisherigen Ableitungsverlauf können nur im einzigen Nichtterminal einer rechten Regelseite kodiert werden.
Somit sind begrenzte Abhängigkeiten zwischen Wortteilen durch die Einführung neuer Nichtterminale darstellbar.
Nicht mehr darstellbar ist jedoch eine unendliche Anzahl von Abhängigkeiten zwischen Wortteilen aufgrund der Forderung
nach kleinen endlichen Alphabeten.
Kann ich jede endliche Sprache durch eine reguläre Grammatik darstellen?
Antwort: Jede endliche Sprache kann durch eine einseitig lineare Grammatik dargestellt werden.
Für jedes Wort wird eine Folge von Regeln eingeführt der Form Rest -> 1-Terminal-von-Rest Rest-neu.
In der Folgeregel nimmt "Rest-neu" die Rolle von "Rest" ein.
Anfänglich ist das Startsymbol "Rest".
Wann enthält die Sprache unendlich viele Wörter?
Antwort: Die Sprache einer einseitig linearen Grammatik ist dann unendlich, wenn es rekursive Regeln gibt.
Eine Regel ist rekursiv, wenn das Nichtterminal der linken Regelseite auch auf der rechten Regelseite vorkommt.
Rekursion kann sich aber auch über mehrere Regeln erstrecken, z.B. A -> aB, B -> bC, C-> cA.
Eine minimale Grammatik für eine unendliche Sprache muss zwei Regeln enthalten:
die rekursive Regel und den Rekursionsabruch, also die Regel, durch die die Rekursion wieder beendet wird.
Wie ist der Zusammenhang zwischen rechts- und linkslinearen Grammatiken?
Antwort: Auf der Wortebene gibt es keinen Unterschied. Die beiden Grammatiktypen leiten die gleichen Sprachen ab.
Nur die Struktur der Wörter, der Ableitungsbaum ist verschieden.
Bei rechtslinearen Grammatiken entsteht ein nach rechts verzweigender Ableitungsbaum.
Bäume von linkslinearen Grammatiken sind linksverzweigend.
| 
1
2
Übersicht: Sprachklassen
