KFG für nicht-Palindrome < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 22:27 Di 21.12.2010 | | Autor: | Scharii |
| Aufgabe | | Geben sie eine erzeugende Grammatik in Chomsky-Normalform für [mm] \{ w \in \{a,b\}^\*|w!=w^r\} [/mm] an. Dabei bezeichnet [mm] w^r [/mm] das Spiegelwort von w. |
Hallo,
Mein Ansatz für die Aufgabe war, erstmal eine KFG zu finden die die Sprache erzeugt, und sie dann in CNF zu bringen.
Nur dabei scheiter ich schon...
Kann mir jemand helfen überhaupt eine Grammatik dafür zu finden, die kontextfrei ist?
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:56 Fr 24.12.2010 | | Autor: | felixf |
Moin!
> Geben sie eine erzeugende Grammatik in Chomsky-Normalform
> für [mm]\{ w \in \{a,b\}^*|w!=w^r\}[/mm] an. Dabei bezeichnet [mm]w^r[/mm]
> das Spiegelwort von w.
EDIT: lesbarer gemacht.
Und was ist "$w!$"?
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:56 Fr 24.12.2010 | | Autor: | Scharii |
[mm] w\in\{a,b\}^\* |w\not=w^r
[/mm]
Ok, der [mm] \* [/mm] steht für den Kleene-Stern, oben ist das aber nur ein Punkt nach den Klammern ... merkwürdig, aber geändert :)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:26 Fr 24.12.2010 | | Autor: | felixf |
Moin,
> [mm]w\in\{a,b\}^\* |w\not=w^r[/mm]
ach, das sollte ein Ungleich sein!
> Ok, der [mm]\*[/mm] steht für den Kleene-Stern, oben ist das aber
> nur ein Punkt nach den Klammern ... merkwürdig, aber
> geändert :)
Das hatte ich mir schon gedacht. Wenn du \ast schreibst, bekommst du auf jeden Fall ein Sternchen.
LG Felix
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:31 Fr 24.12.2010 | | Autor: | felixf |
Moin!
> Geben sie eine erzeugende Grammatik in Chomsky-Normalform
> für [mm]\{ w \in \{a,b\}^\*|w!=w^r\}[/mm] an. Dabei bezeichnet [mm]w^r[/mm]
> das Spiegelwort von w.
>
> Mein Ansatz für die Aufgabe war, erstmal eine KFG zu
> finden die die Sprache erzeugt, und sie dann in CNF zu
> bringen.
> Nur dabei scheiter ich schon...
Erzeuge doch so ein Wort, indem du immer vorne und hinten einen Buchstaben zusammen anfuegst.
Du brauchst zwei Zustaende: einer sagt, das bisher alles symmetrisch ist (also [mm] $w^r [/mm] = w$), und ein zweiter sagt dass es mal nicht der Fall war (das ist sozusagen der "gute" Zustand, von dem aus beendet werden darf).
Also sowas wie (...) -> a(...)a -> ab(...)ba -> abb(...)bba -> abba(...)bbba -> abbaa(...)abbba -> abbaababbba
Hilft dir das weiter?
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 09:47 Di 28.12.2010 | | Autor: | Scharii |
Danke, natürlich geths so...
Hatte nur den Kopf zu verdreht ums zu erkennen :)
Hier meine Lösung in CNF:
S [mm] \to [/mm] AM|BN|AO|BP|AB|BA
M [mm] \to [/mm] SA
N [mm] \to [/mm] SB
O [mm] \to [/mm] ZB
P [mm] \to [/mm] ZA
Z [mm] \to [/mm] AZ|BZ|a|b
A [mm] \to [/mm] a
B [mm] \to [/mm] b
|
|
|
|
