Pumping Lemma < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:19 Mi 06.04.2011 | | Autor: | Loko |
| Aufgabe | Reicht es zu zeigen, dass eine bestimmte Zerlegung pumpbar ist, oder muss es für jede mögliche Zerlegung eines Wortes getestet werden?
Meint die Definition [mm] \forall [/mm] Zerlegungen uvz=w? |
Wenn ich beispielsweise das Wort "w [mm] \textdollar [/mm] trans(w)" habe, dann könnte ich die Zerlegung nach dem Pumping Lemma ja so wählen, dass w = u, v = [mm] \textdollar [/mm] und trans(w) = z ist. Würde jetzt das v gepumpt, läge w [mm] \textdollar^{i} [/mm] trans(w) doch immernoch in der Sprache oder nicht? (Ehrlich gesagt bin ich mir aber auch nicht sicher was genau das [mm] \textdollar-Zeichen [/mm] ist...)
Oder muss für jede mögliche Zerlegung gezeigt werden, dass sie funktioniert? Dann müsste man ja nur zeigen, dass mit dass wenn man v anders als [mm] \textdollar [/mm] wählt es schon nicht mehr funktioniert.
Liebe Grüße :)
Loko
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 11:01 Do 07.04.2011 | | Autor: | felixf |
Moin Loko
> Reicht es zu zeigen, dass eine bestimmte Zerlegung pumpbar
> ist, oder muss es für jede mögliche Zerlegung eines
> Wortes getestet werden?
Wofuer zu zeigen? Um das Pumping Lemma zu beweisen? Dann ja. Wenn das nicht gemeint war, dann musst du dich etwas genauer ausdruecken.
> Meint die Definition [mm]\forall[/mm] Zerlegungen uvz=w?
> Wenn ich beispielsweise das Wort "w [mm]\textdollar[/mm] trans(w)"
> habe, dann könnte ich die Zerlegung nach dem Pumping Lemma
> ja so wählen,
Inwiefern waehlen? Das Pumping Lemma sagt dir, dass es eine Zerlegung gibt. Du kannst sie dir nicht aussuchen.
> dass w = u, v = [mm]\textdollar[/mm] und trans(w) = z
> ist. Würde jetzt das v gepumpt, läge w [mm]\textdollar^{i}[/mm]
> trans(w) doch immernoch in der Sprache oder nicht?
Falls das Pumping Lemma diese Zerlegung liefert, ja. Falls nicht, vermutlich eher nicht.
> (Ehrlich
> gesagt bin ich mir aber auch nicht sicher was genau das
> [mm]\textdollar-Zeichen[/mm] ist...)
Ohne Kontext kann ich dir das auch nicht sagen.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:48 Fr 08.04.2011 | | Autor: | Loko |
Dankeschön.. das hat meine Fragen geklärt. :)
Mit dem $ Zeichen kann ich leider auch nicht wirklich mehr Kontext geben, weil der Dozent es einfach in einem Beispiel verwendet hat. Ich dachte vielleicht ist es ja ein allgemein übliches Zeichen für irgendwas in der Theoretischen Informatik. Aber ist auch nicht allzu wichtig.
Danke jeden Falls!
Lg Loko
|
|
|
|
