meine kontextfreie Grammatik richtig? |
| 16.05.2010, 13:13 | wurmi86 | Auf diesen Beitrag antworten » | ||
| meine kontextfreie Grammatik richtig? ich muss in einer Aufgabe eine kontxtfreie Grammatik angeben. Bin mir aber nicht 100%ig sicher, was genau das bedeutet. Als Narrenerklärung hat mir einer mal gesagt, dass eine kontextfreie Grammatik im Grunge nur eine Einschränkung gegeüber anderen Grammatiken besitzt: Und zwar dass auf der linken Seite einer Bildungsvorschrift nur ein Nichtterminal stehen darf und sonst nix weiter. Auf der rechten seite darf stehen, was will. Ist das richtig? und wenn ja. ist meine Grammatik richtig?: gegeben ist Sprache meine Grammatik ist G={{a,b,c},S,S,R} mit R={S->aS|Sbc|bc, S->bSc|bS|Sc|b|c} hab ich was vergessen? ist überhaupt etwas davon richtig? MfG Wurmi |
||||
| 16.05.2010, 14:37 | Reksilat | Auf diesen Beitrag antworten » | ||
| RE: meine kontextfreie Grammatik richtig? Hi wurmi, Deine Grammatik erzeugt nicht die obige Sprache. Wenn Du mit S beginnst und dann zuerst die Vorschrift S->Sbc und dann S->bc anwendest, dann erhältst Du das Wort bcbc, welches nicht in L liegt. Am besten Du verwendest hier mehrere Nichtterminale; eins für den Fall i=0 und eins für den Fall j=k. Gruß, Reksilat. |
||||
| 16.05.2010, 14:44 | wurmi86 | Auf diesen Beitrag antworten » | ||
| RE: meine kontextfreie Grammatik richtig? Danke Reksilat, also eifnach S->Q|T Q->aQ|Qbc|bc und T->bTc|bT|Tc|b|c und oben in der Definition noch ein Q und T zu den Nichtterminalen, oder? ist das genug? MfG Wurmi |
||||
| 16.05.2010, 14:49 | Reksilat | Auf diesen Beitrag antworten » | ||
RE: meine kontextfreie Grammatik richtig?
Dann hast Du das gleiche Problem, das ich oben geschildert habe, nämlich dass Du bcbcbcbc erhalten kannst. Außerdem musst Du aufpassen, dass das a immer nur am Anfang des Wortes eingefügt werden kann. Da brauchst Du eventuell noch ein Nichtterminal. Der andere Teil ist aber korrekt. |
||||
| 16.05.2010, 14:57 | wurmi86 | Auf diesen Beitrag antworten » | ||
| RE: meine kontextfreie Grammatik richtig? Danke habs begriffen. Q->aQ|D(bzw aD, wenn natürliche zahl ohne 0) D->bDc|bc jetzt aber? =) |
||||
| 16.05.2010, 15:03 | Reksilat | Auf diesen Beitrag antworten » | ||
| RE: meine kontextfreie Grammatik richtig? Da oben auch mal i=0 steht, nehme ich an, dass ist. Damit fehlt dann auch noch die Möglichkeit zu erzeugen (bei Dir wird immer mindestens bc angehängt). Auch das leere Wort sollte erlaubt sein. |
||||
| Anzeige | ||||
|
|
||||
| 16.05.2010, 15:15 | wurmi86 | Auf diesen Beitrag antworten » | ||
| RE: meine kontextfreie Grammatik richtig? alles kalr dankeschön. kann ich ferner z.B. zeigen, dass eine sprache kontextfrei ist, in dem ich eine kontextfreie grammatik angebe 
also ohne Nutzung des Pumping-Lemmas)? |
||||
| 16.05.2010, 15:20 | Reksilat | Auf diesen Beitrag antworten » | ||
| RE: meine kontextfreie Grammatik richtig? Dass eine zugehörige KFG existiert, sollte doch gerade die Definition von kontextfrei sein - demnach: Ja! Dagegen hilft das Pumping-Lemma doch nur dabei, zu zeigen, dass eine Sprache nicht kontextfrei ist. Über die anderer Richtung macht es mMn keine Aussage. Gruß, Reksilat. |
||||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|