kontextfreie Sprache < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:22 Mi 25.11.2009 | | Autor: | mangaka |
| Aufgabe | Sei L eine beliebige kontextfreie Sprache und n die zu L gehörende Konstante aus dem Pumping Lemma. Beweisen Sie:
a) $L [mm] \neq \emptyset \Leftrightarrow \exists [/mm] w [mm] \in [/mm] L: |w| < n$
b) $|L| = [mm] \infty \Leftrightarrow \exists [/mm] w [mm] \in [/mm] L: n [mm] \leq [/mm] |w| < 2n$ |
Moin,
Machen wir's kurz: Hat irgendjemand einen Ansatz für mich?
Ich habe nicht einmal eine Idee wie ich z.B von der nicht leeren Menge zu einem Ausdruck komme, der die Pumping-Lemma Konstante enthält.
Offensichtlich muss man das Lemma iwie anwenden, fragt sich nur wie.
Danke im Voraus.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 04:07 Do 26.11.2009 | | Autor: | felixf |
Hallo!
> Sei L eine beliebige kontextfreie Sprache und n die zu L
> gehörende Konstante aus dem Pumping Lemma. Beweisen Sie:
> a) [mm]L \neq \emptyset \Leftrightarrow \exists w \in L: |w| < n[/mm]
Ist $L = [mm] \emptyset$, [/mm] so gibt es auch kein $w [mm] \in [/mm] L$.
Ist dagegen $L [mm] \neq \emptyset$, [/mm] so gibt es irgendein $z [mm] \in [/mm] L$. Zeige mit dem Pumpinglemma, das aus $|z| [mm] \ge [/mm] n$ folgt, dass es ein Wort $z' [mm] \in [/mm] L$ gibt mit $|z'| < |z|$. Wenn du das genuegend oft machst, bekommst du ein Wort $z'' [mm] \in [/mm] L$ mit $|z''| < n$.
> b) [mm]|L| = \infty \Leftrightarrow \exists w \in L: n \leq |w| < 2n[/mm]
Hier erstmal von mir eine Frage: ist das Alphabet endlich? Oder kann es auch unendlich sein?
Ich vermute mal es ist endlich, ansonsten ist die Implikation [mm] $\Rightarrow$ [/mm] wohl im Allgemeinen falsch.
Angenommen also es ist endlich. Wenn $|L| = [mm] \infty$ [/mm] ist, muss deswegen $L$ beliebig lange Woerter enthalten. Nimm dir eins der Laenge [mm] $\ge [/mm] n$ und konstruiere daraus in endlich vielen Schritten mit Hilfe des Pumping Lemma ein Wort mit Laenge [mm] $\ge [/mm] n$ und $< 2 n$.
Fuer die Rueckrichtung konstruierst du aus einem Wort der Laenge [mm] $\ge [/mm] n$ eine Folge beliebig langer Woerter. (Das folgt sofort aus dem Pumping-Lemma; das ist der allereinfachste Schritt.)
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 10:22 Do 26.11.2009 | | Autor: | mangaka |
Hi,
Danke für die Antwort.
> Zeige mit dem Pumpinglemma, das aus [mm]|z| \ge n[/mm] folgt, dass
> es ein Wort [mm]z' \in L[/mm] gibt mit [mm]|z'| < |z|[/mm].
Das geht doch nur, wenn man als i=0 wählt, oder? ($uv^iwx^iy$).
Das würde ja schon reichen. Man soll ja nur zeigen, dass es ein Wort der Länge kleiner n gibt.
Deine anderen Ausführungen muss ich mir noch einmal genauer ansehen. Melde mich bei Fragen :)
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 10:30 Do 26.11.2009 | | Autor: | felixf |
Hallo!
> > Zeige mit dem Pumpinglemma, das aus [mm]|z| \ge n[/mm] folgt, dass
> > es ein Wort [mm]z' \in L[/mm] gibt mit [mm]|z'| < |z|[/mm].
>
> Das geht doch nur, wenn man als i=0 wählt, oder?
> ([mm]uv^iwx^iy[/mm]).
> Das würde ja schon reichen. Man soll ja nur zeigen, dass
> es ein Wort der Länge kleiner n gibt.
Genau so ist es :)
> Deine anderen Ausführungen muss ich mir noch einmal
> genauer ansehen. Melde mich bei Fragen :)
Ok! Viel Erfolg :)
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 11:01 Do 26.11.2009 | | Autor: | mangaka |
Hab' eine Frage zum Verständnis:
Gilt das:
[mm] $\Sigma [/mm] = [mm] \{a\}$
[/mm]
[mm] $|\Sigma^{*}|=\infty$ [/mm] ? (Gemeint ist [mm] $\Sigma$-Stern)
[/mm]
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 11:05 Do 26.11.2009 | | Autor: | felixf |
Hallo!
> Hab' eine Frage zum Verständnis:
> Gilt das:
> [mm]\Sigma = \{a\}[/mm]
> [mm]|\Sigma^\ast|=\infty[/mm] ?
Ja: [mm] $\Sigma^\ast [/mm] = [mm] \{ \varepsilon, a, aa, aaa, aaaa, aaaaa, \dots \}$
[/mm]
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 11:30 Do 26.11.2009 | | Autor: | mangaka |
Hat es eigentlich einen tieferen Sinn, dass die Bedingung u.a. $|w| < 2n$ lautet?
Sonst habe ich deinen Gedankengang bisher nachvollziehen können.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:26 Do 26.11.2009 | | Autor: | felixf |
Hallo!
> Hat es eigentlich einen tieferen Sinn, dass die Bedingung
> u.a. [mm]|w| < 2n[/mm] lautet?
> Sonst habe ich deinen Gedankengang bisher nachvollziehen
> können.
Nun, man kann natuerlich auch ein Wort der Laenge [mm] $\ge [/mm] 2 n$ finden, das reicht auch.
Aber solche Charakterisierungen sind halt nett, wenn man die Laenge des Wortes so kurz wie moeglich halten kann. Deswegen hast du da die $< 2 n$ stehen.
LG Felix
|
|
|
|
