Diskussion:Reguläre Grammatik

Alte Diskussion

Dieser Artikel sollte (und so ist es geplannt) mit selbigen Thema gefüllt werden, also aus Chomsky-Hierarchie herausgearbeitet werden ;) --Kleinvieh macht auch Mist 18:12, 29. Nov 2005 (CET)

Na ja, ist ganz nett und knapp bei der Chomsky-Hierarchie definitert. Und unter Reguläre Sprache steht auch ganz viel. Hier genügt vielleicht ein paar Verweise, nehme ich auf! --WiseWoman 18:44, 17. Dez 2005 (CET)

Ich denke hier steht aber etwas falsches: Und zwar ist eine reguläre Grammatik nicht kontextsensitiv und auch nicht vom Typ-2. Sondern von Typ3. Wie schon richtig steht ist eine reguläre Grammatik einseitig linear und das ist eindeutig Typ3.

Leeres Wort

So wie "reguläre Grammatik" momentan definiert ist, können damit keine Sprachen erzeugt werden, die das leere Wort enthalten. Jemand mit Zugang zu einem einschlägigen Fachbuch sollte diesen Punkt noch korrigieren. Gruß, Wasseralm 19:49, 5. Jul. 2007 (CEST)

Beispiel: Lineare Grammatiken

Sie produziert die (in diesem Fall reguläre) Sprache $0^{n}1^{n}$.

Die erzeugte Sprache ist wohl kontextfrei, aber keine reguläre Sprache. Auffällig ist, dass die Grammatik nur aus regulären Regeln besteht, jedoch sowohl links- als auch rechtsreguläre. --Johannes Koch 06:25, 27. Feb. 2008 (CET)

• Hm? Wieso sollte $0^{n}1^{n}$ nicht regulär sein? Du meinst sicher, dass lineare Grammatiken im allgemeinen Fall nicht notwendigerweise reguläre Sprachen erzeugen. Wir hatten das neulich in der Löschdiskussion, die Geschichte mit den linearen Grammatiken gehört im Grunde hier raus und in einen eigenen kurzen Artikel. Ich hoffe, ich komme an einem der nächsten Abende dazu. --Mussklprozz 07:04, 27. Feb. 2008 (CET)

• • Nach meinem Verständnis ist $0^{n}1^{n}$ nur kontextfrei. Ein EA würde unendlich viele Zustände benötigen um alle Wörter der Sprache erkennen zu können. Oder stehe ich nun komplett auf dem Schlauch? --Johannes Koch 17:23, 27. Feb. 2008 (CET)

• • • Ich war derjenige, der auf der Leitung stand, bzw. nicht genau genug hingeguckt hat. $0^{n}1^{n}$ und $0^{n}1^{m}$ ist ein kleiner feiner Unterschied ... --Mussklprozz 18:15, 27. Feb. 2008 (CET)

"Regulär"?

Was deutet der Begriff "regulär" in "Reguläre Grammatik" an? regulär bedeutet den Regeln, Vorschriften oder einer Ordnung entsprechend, aber diese "Eigenschaften" haben andere Grammatiken (kontextfreie, kontextsensitive etc.) doch auch. --Abdull 00:35, 31. Aug. 2010 (CEST)

Das ist wie so oft in der Mathematik: Man nahm ein kurzes, griffiges, gebräuchliches Wort, um einer abstrakten Struktur einen Namen zu geben. Man könnte sich auch fragen, was an einem Ring so besonders rund und an einem Körper so besonders massiv ist. --Mussklprozz 07:24, 31. Aug. 2010 (CEST)

Wenn man dazu Goethe zitieren darf: „Die Mathematiker sind eine Art Franzosen: Redet man zu ihnen, so übersetzen sie es in ihre Sprache, und dann ist es alsobald ganz etwas anders. ” (Maximen 1005)

Man sollte sich klarmachen, dass die erborgten Worte zwar Konnotationen aus der Allltagssprache mitschleppen, diese aber in der neuen Verwendung nicht mehr gelten sollen; wer sich auf eine solche verlässt, geht dann irre. Alles, was gemeint ist, steht ausdrücklich und ausschließlich in der Definition des Begriffs. Es geht dabei so dreist zu wie bei Alice: „A word just means what I want it to mean.” -- Silvicola Diskussion Silvicola 13:35, 31. Aug. 2010 (CEST)

Regelverletzung beim Beispiel

Im Beispiel zum Ableitungsvorgang (http://de.wikipedia.org/wiki/Regul%C3%A4re_Grammatik#Beschreibung_des_Ableitungsvorgangs) gibt es sowohl die Regel $S\rightarrow \varepsilon$ als auch das Startsymbol auf der rechten Seite von Produktionsregeln. Laut http://de.wikipedia.org/wiki/Chomsky-Hierarchie#Definition_2 ist das verboten ("Als einzige Ausnahme von dieser Forderung lässt man $S\rightarrow \varepsilon$ zu, wenn das Startsymbol nirgends auf der rechten Seite einer Produktion auftritt.")

Ich habe im Moment keine Zeit das Beispiel zu korrigieren, könnte mich aber nach der Prüfungszeit dransetzen. (nicht signierter Beitrag von 79.250.127.58 (Diskussion) 13:14, 18. Aug. 2011)

Das Beispiel stimmt hinten und vorne nicht. Der Automat erkennt nicht die Sprache $L_{doremi}=\{do\}^{*}\cup \{re\}^{*}\cup \{mi\}^{*}$. Die enthält nämlich nur beliebige Wiederholungen von do, re, oder mi, also beispielsweise dodo, rererere, mimimi, aber keine Zusammensetzungen aus diesen Silben. $domire\notin L_{doremi}$, entgegen dem, was im Beispiel behauptet wird. --Mussklprozz 13:30, 18. Aug. 2011 (CEST)

Eigentlich hätte man bloß $L_{doremi}=\{do\}^{*}\cup \{re\}^{*}\cup \{mi\}^{*}$ durch $L_{doremi}=\{do,re,mi\}^{*}$ ersetzen müssen. Dann stimmt das ganze Beispiel, und sinnvoller ist diese Sprache sowieso (jedenfalls, wenn man ihr den Namen L_doremi gibt, was ja mit Musik zu tun hat. mimimimimimimimi ist keine schöne Melodie! ;) )

Hab's auch gleich mal gemacht.

Das mit der Rückkehr nach S ist natürlich noch falsch, das lässt sich aber leicht ändern, wenn man mal vom Bild absieht. --Daniel5Ko 13:53, 18. Aug. 2011 (CEST)

Nun hab' ich ein Nicht-Terminal S' hinzugefügt. Alternativ hätte man auch $L_{doremi}=\{do,re,mi\}^{+}$ definieren, und das Epsilon aus der Regel für S herausnehmen können. So oder so passt der Automat allerdings nicht... --Daniel5Ko 14:08, 18. Aug. 2011 (CEST)

Und nun hab' ich gemerkt, dass die Rückkehr zum Startsymbol mit Epsilon erlaubt und kein Problem ist. Sorry für's hin-und-her. Was 79.250 zitierte, gilt für kontextsensitive Grammatiken. --Daniel5Ko 14:21, 18. Aug. 2011 (CEST)

Danke für die Mühe! L_doremi klingt übrigens hübsch, erinnert an El Dorado. ;-) --Mussklprozz 15:32, 18. Aug. 2011 (CEST)

Ich hatte das Bild mit Beispiel eingebaut, das Bild stammt aber nicht von mir. Ich habe die Grammatik dazu aufgeschrieben und leider die Sprache falsch angegeben. Danke für die Korrektur. In regulären Grammatiken, kontextfreien Grammatiken und unter Umständen auch kontextsensitiven Grammatiken ist die Regel $S\rightarrow \varepsilon$ je nach Definition ohne Einschränkungen möglich. Das Problem kommt durch die Gleichstellung von den jeweiligen Grammatiken mit den Typen aus der Chomsky-Hierarchie. Nach Chomsky ist ab Typ 1 jegliche Regel $X\rightarrow \varepsilon$ verboten. Somit ist eigentlich keine der Chomsky-Grammatiken mit den oben genannten Grammatiken identisch, aber Ausnahmen für das leere Wort werden dann meistens in verschiedenen Varianten angenommen. Das hat zur Folge, dass die Beziehung "Typ 0 enthält Typ 1 enthält Typ 2 enthält Typ 3" für Sprachen noch gilt, aber für Grammatiken nicht mehr.

Man sollte vermutlich konsequent das Verhältnis zur Chomsky-Hierarchie besser darstellen, aber das wird in der Literatur nicht so gemacht. --Zahnradzacken 18:03, 18. Aug. 2011 (CEST)