# kontextfreie grammatik / reguläre grammatik



## BlubBlub (3. Sep 2009)

also ich les grad ein paar sachen über xml in meinem skript.
und da steht, dass ein Data-Guide von einen Baum abgeleitet wird und selbst ein Baum ist.
Dieser Baum stellt eine kontextfreie grammatik dar.

nun steht weiter, dass die DTD zu diesem baum eine reguläre grammatik darstellt.
auf wikipedia steht, dass die reguläre grammatik eine spezialisierte form der kontextfreien grammatik ist.
die reguläre grammatik besteht aus vier tupeln (Nichtterminale, Terminale, Produktionen, Startsymbol) und die kontextfreie grammatik besteht ebenfalls aus diesen vier tuppeln.

der unterschied zwischen den beiden ist laut wikipedia, dass die reguläre grammatik entweder rechts oder linksregulär ist, dass heißt:

A = Aa bzw A =aA
B = Bb  bzw B =bB

nicht erlaubt ist bei einer regulären Grammatik:

A = Aa
B = bB

man muss sich entscheiden ob man linksregulär alles aufbaut bzw. rechtsregulär

zudem ist verboten:

A = aAa 

Bei der kontextfreiengrammatik legt man sich nicht fest auf links oder rechtsregularität, 
da ist alles erlaubt also:

erlaubt:
A = Aa
B = bB
A = aAa 


Das sind so die informationen die ich mir so zusammengesucht hab und so interpretiert hab.

meine frage: hab ich das alles richtig interpretiert? und vorallem besteht sowohl die reguläre als auch die kontextfreie grammatik aus den selben vier tuppeln?
unterscheiden sich diese beiden grammatiken tatsächlich NUR in den erlaubten produktionen (siehe meine beispiele)?


----------



## Ark (3. Sep 2009)

Nun, ich würde mal behaupten, alle formalen Grammatiken bestehen aus den von dir genannten vier Teilen. Die Unterscheidungen werden wirklich nur anhand der erlaubten Produktionen getroffen.

Ganz grob und ohne Berücksichtigung einiger "Spezialfälle"/Details (Epsilon etc.), in Klammern steht bildlich(!) beschrieben, wie sich die Einschränkung gegenüber dem vorangegangenen Typ äußert:


Typ 0: Alles ist erlaubt; natürlich sollte aber links mindestens ein Nichtterminal stehen.
Typ 1: Linke Seite darf nicht länger sein als rechte. (Der Text wird beim Lesen nicht mehr länger.)
Typ 2: Linke Seite hat nur genau ein Nichtterminal. (Im Text gibt es kein Vorher und kein Nachher mehr.)
Typ 3: Rechte Seite hat nur höchstens ein Nichtterminal und dieses entweder immer ganz links oder immer ganz rechts. (Es gibt keine hierarchischen Abhängigkeiten zwischen Wörtern mehr.)
Ich denke schon, dass du das so weit richtig interpretiert hast. Deine Beispiele erscheinen mir jedoch etwas sehr eingeschränkt (verglichen mit dem, was ich gerade zur Chomsky-Hierarchie geschrieben habe. Keine Garantie auf Richtigkeit! Vollständig ist es sowieso nicht).

Ark


----------



## BlubBlub (5. Sep 2009)

alles klar danke für die antwort


----------

