kontextfreie Grammatik->reguläre Sprache? |
| 09.06.2007, 16:41 | Auf diesen Beitrag antworten » |
| RegEx | 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 |
|
|
|
| 09.06.2007, 19:15 | Auf diesen Beitrag antworten » |
| qwertz | 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... 
|
| 09.06.2007, 19:46 | Auf diesen Beitrag antworten » |
| RegEx | RE: kontextfreie Grammatik->reguläre Sprache? Hallo qwertz, ja, Du liegst mit deinen Vermutungen beide Male richtig :-) Grüße, RegEx |
| 09.06.2007, 20:48 | Auf diesen Beitrag antworten » |
| qwertz | 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... |
| Anzeige | |
|
|
|
| 10.06.2007, 16:32 | Auf diesen Beitrag antworten » |
| RegEx | 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 |
| 20.06.2007, 12:54 | Auf diesen Beitrag antworten » |
| qwertz | 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. |
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
| Die Neuesten » |
|
