Pumping Lemma,reguläre Sprache < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 20:08 Di 16.11.2010 | | Autor: | Lovelace |
| Aufgabe | Gegeben sei die Sprache A= [mm] (c^iaba^jb^k [/mm] |i, j, k [mm] \ge [/mm] 1 und i= 2j oder i = k)
a) Geben Sie eine Grammatik vom Typ 2 an, die A erzeugt
b) Zeigen Sie mit dem Algorithmus von Cocke, Younger und Kasami, dass das Wort cabab in A ist
c) Zeigen Sie mit Hilfe des Pumpinglemmas, dass A nicht regulär ist. |
Okay, a) habe ich denke ich hinbekommen, allerdings ist meine Grammatik leider sehr kompliziert...vielleicht hat mir da jemand einen Tipp für einfacheren Ansatz?
meine Grammatik sieht so aus:
S --> AB | aCb
A --> cAaa | cEaa
E --> ab
B --> bB | b
C --> aCb | abF
F --> aF | a
Meiner Meinung nach müsste das funktionieren...allerdings habe ich ganz schöne Probleme bekommen, das in CNF umzuwandeln um die b) lösen zu können ... (hat dann auch nicht geklappt...:-( )
Und bei c) komme ich irgendwie auch nicht weiter...
Anfangen muss ich ja immer mit der Annahme, A wäre regulär, dann gäbe es eine Zahl n, sodass ich alle Wörter x [mm] \in [/mm] L mit |x| [mm] \ge [/mm] n zerlegen lassen in x= uvw für die gilt:
(i) |v| [mm] \ge [/mm] 1 (--> v ist also nicht leer)
(ii) |uv| [mm] \ge [/mm] n
(iii) für alle i = 1, 2, 3, ... gilt uv^iw [mm] \in [/mm] L
--> und jetzt hört es auf...was wäre denn geschickt, wie ich mein n hier wählen könnte?! Da komm ich nicht weiter...
Vielen vielen Dank für die Hilfe! Tut mir Leid, dass ich heute so viel posten muss, aber wie gesagt...Prüfungsvorbereitung...
Liebe Grüße,
Ada
P.S.: Frage ist nirgendwo sonst von mir gepostet worden!
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 20:58 Di 16.11.2010 | | Autor: | felixf |
Moin Ada!
> Gegeben sei die Sprache A= [mm](c^iaba^jb^k[/mm] |i, j, k [mm]\ge[/mm] 1 und
> i= 2j oder i = k)
>
> a) Geben Sie eine Grammatik vom Typ 2 an, die A erzeugt
>
> b) Zeigen Sie mit dem Algorithmus von Cocke, Younger und
> Kasami, dass das Wort cabab in A ist
>
> c) Zeigen Sie mit Hilfe des Pumpinglemmas, dass A nicht
> regulär ist.
> Okay, a) habe ich denke ich hinbekommen, allerdings ist
> meine Grammatik leider sehr kompliziert...vielleicht hat
> mir da jemand einen Tipp für einfacheren Ansatz?
>
> meine Grammatik sieht so aus:
> S --> AB | aCb
> A --> cAaa | cEaa
> E --> ab
> B --> bB | b
>
> C --> aCb | abF
> F --> aF | a
>
> Meiner Meinung nach müsste das funktionieren...
Leider nicht: das Wort $cabab$ (mit $i = 1$, $j = 1$, $k = 1$) kann nicht erzeugt werden.
> allerdings
> habe ich ganz schöne Probleme bekommen, das in CNF
> umzuwandeln um die b) lösen zu können ... (hat dann auch
> nicht geklappt...:-( )
Was ist CNF? Hoert sich nach einer Normalform an...
> Und bei c) komme ich irgendwie auch nicht weiter...
>
> Anfangen muss ich ja immer mit der Annahme, A wäre
> regulär, dann gäbe es eine Zahl n, sodass ich alle
> Wörter x [mm]\in[/mm] L mit |x| [mm]\ge[/mm] n zerlegen lassen in x= uvw
> für die gilt:
> (i) |v| [mm]\ge[/mm] 1 (--> v ist also nicht leer)
> (ii) |uv| [mm]\ge[/mm] n
Du meinst $|u v| [mm] \le [/mm] n$.
> (iii) für alle i = 1, 2, 3, ... gilt uv^iw [mm]\in[/mm] L
>
> --> und jetzt hört es auf...was wäre denn geschickt, wie
> ich mein n hier wählen könnte?! Da komm ich nicht
> weiter...
Nimm doch das Wort $x = [mm] a^{2 n} [/mm] a b [mm] a^n [/mm] b$.
Was kannst du ueber $u$ und $v$ aussagen?
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 00:51 Do 18.11.2010 | | Autor: | Lovelace |
Hallo Felix!
Vielen vielen Dank erst mal für deine Hilfe! Ich weiß garnicht, was ich sonst machen würde!
Zum Pumping Lemma habe ich noch eine Frage: Gibt es da irgendeinen "Trick" oder eine Strategie, aus der ich schließen kann, wie ich n immer wählen sollte??? Irgendwie kann ich das noch nicht so richtig "fassen"...
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 02:03 Do 18.11.2010 | | Autor: | felixf |
Moin!
> Vielen vielen Dank erst mal für deine Hilfe! Ich weiß
> garnicht, was ich sonst machen würde!
>
> Zum Pumping Lemma habe ich noch eine Frage: Gibt es da
> irgendeinen "Trick" oder eine Strategie, aus der ich
> schließen kann, wie ich n immer wählen sollte???
> Irgendwie kann ich das noch nicht so richtig "fassen"...
Das $n$ kannst du nicht waehlen, das liefert dir das Pumping-Lemma. Das $n$ gibt es einfach.
Der Trick ist eher, ein Wort (abhaengig von $n$) passend zu waehlen.
Und ich glaube, das ist aehnlich wie beim Integrieren: es gibt kein "Schema-F", sondern man muss probieren und moeglichst viele Beispiele rechnen, damit man eine Art "Intuition" bekommt.
Ich hab zum Beispiel versucht das Wort so zu waehlen, dass die Bedingungen aus der Sprache verletzt werden wenn man es weit genug aufblaeht.
LG Felix
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:01 Di 16.11.2010 | | Autor: | felixf |
Moin!
> meine Grammatik sieht so aus:
> S --> AB | aCb
> A --> cAaa | cEaa
> E --> ab
> B --> bB | b
>
> C --> aCb | abF
> F --> aF | a
>
> Meiner Meinung nach müsste das funktionieren...allerdings
> habe ich ganz schöne Probleme bekommen, das in CNF
> umzuwandeln um die b) lösen zu können ... (hat dann auch
> nicht geklappt...:-( )
Also CNF = ![[]](/images/popup.gif) Chomsky-Normalform?
Dann kannst du z.B. die Regel $S [mm] \to [/mm] a C b$ ersetzen durch:
$S [mm] \to S_1 S_2$
[/mm]
[mm] $S_1 \to [/mm] a$
[mm] $S_2 \to [/mm] C [mm] S_3$
[/mm]
[mm] $S_3 \to [/mm] b$
Und die Regel $A [mm] \to [/mm] cAaa$ durch
$A [mm] \to A_1 A_2$
[/mm]
[mm] $A_1 \to A_3 [/mm] A$
[mm] $A_3 \to [/mm] c$
[mm] $A_2 \to A_4 A_4$
[/mm]
[mm] $A_4 \to [/mm] a$
usw.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 00:55 Do 18.11.2010 | | Autor: | Lovelace |
Jupp, Chomsky-Normalform ist was ich damit meine...die Umformung bekomme ich denke ich auch hin, es hat nur nicht geklappt gehabt mit meinem Algorithmus danach, um das Wortproblem zu lösen...was daran liegen könnte, das meine Grammatik doch ziemlich kompliziert war...aber wie ich es leichter machen könnte weiß ich auch nicht.
hatte hier einen kleinen Tippfehler drin, in der ersten Zeile muss es natürlich
S --> AB | cCb heißen...dann klappt es auch mit cabab mit der Grammatik zu erzeugen!
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 02:07 Do 18.11.2010 | | Autor: | felixf |
Moin,
> Jupp, Chomsky-Normalform ist was ich damit meine...die
> Umformung bekomme ich denke ich auch hin, es hat nur nicht
> geklappt gehabt mit meinem Algorithmus danach, um das
> Wortproblem zu lösen...was daran liegen könnte, das meine
> Grammatik doch ziemlich kompliziert war...aber wie ich es
> leichter machen könnte weiß ich auch nicht.
also eigentlich sollte es unabhaengig davon funktionieren, wie kompliziert die Grammatik ist. Kann halt nur eventuell sehr lange dauern, bis man das Ergebnis bekommt 
LG Felix
|
|
|
|
