Ich fang mal von vorne an
.
Eine Grammatik in diesem Sinne ist ja definiert als ein 4-Tupel (N, T, S, P). Dabei ist N eine Menge von nichtterminalen Symbolen, T die Menge der Terminalen Symbole, S ein Element aus N, das "Startsymbol" und P eine Menge von Ableitungsregeln. Ein Wort w gehört zur Sprache, die durch diese Grammatik erzeugt wird, wenn es eine Abfolge von Regeln gibt mit S ->* w und w enthält nur Zeichen aus T.
Oft (wenn es nur um das Prinzip geht) werden terminale Symbole mit Kleinbuchstaben, Nichterminale mit Großbuchstaben gekennzeichnet. Bei konkreten Beispielen hat man aber auch Nichterminale Symbole wie ZIFFER, ZAHL, AUSDRUCK, und als terminale Symbole z.B. (,),*,+,-,:,0,1,2,3,4,5,6,7,8,9,. Man könnte auch ein Symbol LECKERER_APFELKUCHEN_NACH_OMAS_ALTEM_HAUSREZEPT definieren - auch wenn das ziemlich lang aussieht, wäre das dann nur ein Symbol
.
Die Ableitungsregeln sind nun von der Form (N+T)* -> (N+T)*, d.h. durch die Anwendung der Regel wird eine Zeichenkombination aus terminalen und nichtterminalen Symbolen durch eine andere Kombination dieser Zeichen ersetzt. In der Chomsky-Hierarchie werden nun Einschränkungen definiert, wie diese Regeln aussehen dürfen.
Die Anzahl der Worte ist bei jeder Regel bei jedem Typ gleich: links eins, und rechts eins. Den Unterschied machen die Anzahl der Symbole in diesen beiden Worten aus.
Typ-1-Grammatiken dürfen nur Regeln enthalten, bei denen die zu ersetzende Zeichenkombination nicht länger ist als die ersetzende. D.h., durch die Anwendung einer Regel wird ein "unfertiges Wort" nicht kürzer.
Meine kleine Grammatik von eben hat ein Nichtterminales Symbol S, was auch das Startsymbol ist, vier Terminale Symbol a,b,d,e und vier Ableitungsregeln S -> aSa, S-> bSb, S-> d und aSa -> edde (oben habe ich eine verkürzende Schreibweise benutzt
). Bei den ersten drei Regeln steht auf der linken Seite nur ein Symbol (das S), und rechts drei oder ein Symbol. Bei der vierten Regel stehen links drei Symbole, und rechts vier. Damit ist die Bedingung für Typ-1-Grammatiken erfüllt. (Laut Wikipedia muss zusätzlich gelten, dass links mindestens ein Symbol aus N stehen muss. Das halte ich aber nur für bedingt sinnvoll, da man (glaube ich) jede Grammatik so umschreiben kann, dass in jeder Regel links
nur Symbole aus N stehen.
)
Die Sprache, die diese Grammatik definiert sind Palindrome aus den Zeichen a und b, deren Mitte markiert ist mit d (falls die Länge ungerade ist) oder mit aeddea (falls die Länge gerade ist).
