Informatiker Board | Theoretische Informatik | kontextfreie Grammatik->reguläre Sprache?

Informatiker Board » Themengebiete » Theoretische Informatik » kontextfreie Grammatik->reguläre Sprache?

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

kontextfreie Grammatik->reguläre Sprache?

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

RegEx
Grünschnabel

Dabei seit: 09.06.2007
Beiträge: 4

kontextfreie Grammatik->reguläre Sprache?

Zitatantwort auf diesen Beitrag erstellen

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

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von RegEx: 09.06.2007 17:04.

09.06.2007 16:41

Nehmen Sie RegEx in Ihre Freundesliste auf

qwertz
Grünschnabel

Dabei seit: 01.06.2007
Beiträge: 4

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... verwirrt

09.06.2007 19:15

Nehmen Sie qwertz in Ihre Freundesliste auf

RegEx
Grünschnabel

Dabei seit: 09.06.2007
Beiträge: 4

RE: kontextfreie Grammatik->reguläre Sprache?

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

09.06.2007 19:46

qwertz
Grünschnabel

Dabei seit: 01.06.2007
Beiträge: 4

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 großes Grinsen

.

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...

09.06.2007 20:48

RegEx
Grünschnabel

Dabei seit: 09.06.2007
Beiträge: 4

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

RegEx hat dieses Bild (verkleinerte Version) angehängt:

10.06.2007 16:32

qwertz
Grünschnabel

Dabei seit: 01.06.2007
Beiträge: 4

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.

20.06.2007 12:54

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » kontextfreie Grammatik->reguläre Sprache?