---

Geschrieben von RegEx am 09.06.2007 um 16:41:

  kontextfreie Grammatik->reguläre Sprache?

Hallo,
ich habe folgende Aufgabe zu lösen:
Die Sprache L über dem Alphabet {a,b,c} ist definiert durch die folgende kontextfreie Grammatik(Startsymbol A)

A: aA;
A: B;
A: cC;
B: cB;
B: b;
C: Cc;
C: ;

Frage: ist die Sprache L regulär? Begründen Sie ihre Antwort.

Könnt ihr mir das beantworten? Ich komm da leider nicht dahinter woran ich das erkennen soll...

Grüße,
RegEx

---

Geschrieben von qwertz am 09.06.2007 um 19:15:

  RE: kontextfreie Grammatik->reguläre Sprache?

Kannst du vllt erläutern was du mit
A: aA;
A: B;
meinst?

Soll das A -> aA | B bedeuten (also "A geht über in aA oder B")?

Und was bedeutet "C: ;"?
C -> Epsilon (leeres Wort)?

Habe diese Art der Notation noch nie gesehen...

---

Geschrieben von RegEx am 09.06.2007 um 19:46:

  RE: kontextfreie Grammatik->reguläre Sprache?

Hallo qwertz,
ja, Du liegst mit deinen Vermutungen beide Male richtig :-)
Grüße,
RegEx

---

Geschrieben von qwertz am 09.06.2007 um 20:48:

  RE: kontextfreie Grammatik->reguläre Sprache?

Ich würd' mal spontan behaupten, dass die Sprache regulär ist, weil man für sie einen regulären Ausdruck angeben kann:
a*c*b + a*c*

Alternativ kann man auch einen endlichen Automaten basteln, der die Sprache akzeptiert. Auf Wunsch kann ich mal die Übergangsfunktionen posten, aber nicht mehr heute Abend .

Etwas verwirrend finde ich nur die Regel "C: Cc;".
Hast du dich da evtl. vertippt? Sollte die Regel vllt. C->cC heißen?
Falls nein, dann wäre die Grammatik nämlich gleichzeitig rechts- und linkslinear, bin mir nicht sicher ob das" erlaubt" ist...

---

Geschrieben von RegEx am 10.06.2007 um 16:32:

  RE: kontextfreie Grammatik->reguläre Sprache?

Hallo qwertz,
ich komm da auf einen anderen RegEx, ich hab meine Lösung als Bild angehängt.
Grüße,
RegEx

---

Geschrieben von qwertz am 20.06.2007 um 12:54:

  RE: kontextfreie Grammatik->reguläre Sprache?

In deiner Lösung fehlt aber Folgendes:

-linker Teil:
die Wdh. von a und c (also a* und c*), obwohl sie in deinem Automat
enthalten ist; außerdem setzt du voraus, dass das Wort auf jeden Fall mit einem a beginnen muss, was aber nicht der Fall ist, da ein einfaches c auch in der Sprache liegt (A -> cC -> c)

-rechter Teil:
man kann das Wort aacb (oder ein anderes Wort, das mit a beginnt und mit b endet) nicht erzeugen, obwohl es in der Sprache liegt
(Ableitung für aacb:
A -> aA -> aaA -> aaB -> aacB -> aacb)

Meine Lösung hat auch einen kleinen Fehler, der Ausdruck müsste nämlich a*c*b + a*c+ (also mind. ein c) lauten.