kontextfreie Grammatik < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:11 Mo 08.12.2008 | | Autor: | Hausi |
| Aufgabe | | Geben Sie jeweils eine CFG (context-free Grammer) für die Sprache [mm] L = \{ww^R | w \in \{a,b\}^\* \}[/mm] und [mm] \overline{L}[/mm] an. (Palindrome) |
Hallo,
offensichtlich handelt es sich hierbei um die Sprache der Palindrome mit gerader Anzahl Buchstaben, also w gefolgt von w gespiegelt.
Klar ist mir auch, wie L aussieht, nämlich (vereinfachend nur die Produktionsregeln der Grammatik mit S Startsymbol):
[mm] S \rightarrow aSa , bSb , \epsilon [/mm]
Aber wie kann ich jetzt davon [mm]\overline{L}[/mm] (also das Komplement) bilden?
Ich dachte mir, dass ich also in meiner Grammatik irgendwie etwas einbauen muss, dass beim Palindrom erzeugen mindestens einen oder beliebig viele Fehler macht, also denke ich mir, dass ich etwa eine solche Regel mind einmal, oder auch beliebig oft zwischendurch ausführen kann:
[mm] T \rightarrow VaXbW , VbXaW [/mm] (so ist irgendwo ein "Fehler" mindestens drin) und V, X, W das beliebig weiterbilden könnten, jedoch V und W gleich lang sein müssen und X gerade bleibt. Aber so komme ich da nicht ganz weiter ... vielleicht brauche ich einen ganz anderen Ansatz beim Komplement und es ist bestimmt total einfach und komme so nicht drauf?
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 13:35 Mo 08.12.2008 | | Autor: | bazzzty |
> Aber wie kann ich jetzt davon [mm]\overline{L}[/mm] (also das
> Komplement) bilden?
Da bin ich jetzt auch gerade ins Grübeln gekommen..
> Ich dachte mir, dass ich also in meiner Grammatik irgendwie
> etwas einbauen muss, dass beim Palindrom erzeugen
> mindestens einen oder beliebig viele Fehler macht, also
> denke ich mir, dass ich etwa eine solche Regel mind einmal,
> oder auch beliebig oft zwischendurch ausführen kann:
Was Du gesagt hast, ist genau richtig: Man erzeugt ein Nicht-Palindrom, indem man eine Zeit lang ein Palindrom erzeugt, dann mindestens einen Fehler macht, und dann noch ein beliebiges Wort erzeugt. Vielleicht reicht das ja schon, ansonsten kommt weiter unten noch ein Tipp.
.
.
.
.
.
.
.
.
.
.
.
Der Tipp ist, daß sich jedes Wort, das kein Palindrom ist, zerlegen läßt in
[mm]waxbw^T[/mm] oder [mm]wbxaw^T[/mm] für [mm]w,x\in \{a,b\}^*[/mm].
|
|
|
|
