Pumping-Lemma < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 01:42 So 12.12.2010 | | Autor: | Loko |
| Aufgabe | Zeige mit Hilfe des Pumping-Lemmas, dass die folgende Sprache nicht regulär ist:
{w [mm] \in {a,b}^{*} [/mm] | 2*(Anzahl von a in w) = 3*(Anzahl von b in w)} |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Bei einer anderen Sprache habe ich es geschafft das zu zeigen, hier ist mir aber nicht klar wie man überhaupt das Wort allgemein mit w = xyz zerteilen kann. Also wie man x und y wählen kann, da ja nur die Anzahl stimmen muss und alle Kombinationen der a's und b's möglich sind.
Ich hab also noch keinen Ansatz...
Lg
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 02:34 So 12.12.2010 | | Autor: | felixf |
Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
Moin!
> Zeige mit Hilfe des Pumping-Lemmas, dass die folgende
> Sprache nicht regulär ist:
>
> {w [mm]\in {a,b}^{*}[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
| 2*(Anzahl von a in w) = 3*(Anzahl von b
> in w)}
>
> Bei einer anderen Sprache habe ich es geschafft das zu
> zeigen, hier ist mir aber nicht klar wie man überhaupt das
> Wort allgemein mit w = xyz zerteilen kann. Also wie man x
> und y wählen kann, da ja nur die Anzahl stimmen muss und
> alle Kombinationen der a's und b's möglich sind.
> Ich hab also noch keinen Ansatz...
Na, du kannst dir doch das Wort $w$ aussuchen -- in Abhaengigkeit von der Zahl $n$ aus dem Pumpinglemma. Und du weisst, dass $y \neq \varepsilon$ ist und $|x y| \le n$ ist. Wenn etwa $w$ mit mindstens $n$ $a$s anfaengt, weisst du, dass $x$ und $y$ nur aus $a$s bestehen.
Damit bekommst du doch schnell einen Widerspruch.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 03:02 So 12.12.2010 | | Autor: | Loko |
| Aufgabe | Zeige mit Hilfe des Pumping-Lemmas, dass die folgende Sprache nicht regulär ist:
{w $ [mm] \in {a,b}^{\*} [/mm] $ | 2*(Anzahl von a in w) = 3*(Anzahl von b in w)} |
ich definierte mein w dann so:
w = [mm] a^{3n}b^{2n} [/mm] (s.d 2 [mm] \* [/mm] Anzahl von a = 3 [mm] \* [/mm] Anzahl von b ist)
Dann müssten wegen |xy| [mm] \le [/mm] n x und y lauter a's sein (wie du schon gesagt hast).
Also ist
x:= [mm] a^{j}, y:=a^{k}, [/mm] dann z:= [mm] a^{2n}b^{2n} [/mm] mit k>0, j [mm] \le [/mm] 0 und k + j = n.
[mm] \Rightarrow w_{i} [/mm] = [mm] a^{j}(a^{k})^{i} a^{2n}b^{2n} [/mm] = [mm] a^{3n+(i-1)k}b^{2n}.
[/mm]
für i = 0: [mm] w_{0} [/mm] = [mm] a^{3n-k}b^{2n} [/mm] also nicht [mm] \in [/mm] L.
[mm] \Rightarrow [/mm] L nicht regulär.
Ist das so richtig? (Natürlich noch nicht richtig ausformuliert..)
Vielen Dank und Lg!
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 03:29 So 12.12.2010 | | Autor: | felixf |
Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
Moin!
> Eingabefehler: "{" und "}" müssen immer paarweise
> auftreten, es wurde aber ein Teil ohne Entsprechung
> gefunden (siehe rote Markierung)
>
> Zeige mit Hilfe des Pumping-Lemmas, dass die folgende
> Sprache nicht regulär ist:
>
> {w [mm]\in {a,b}^{\*} [/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
Eingabefehler: "{" und "}" müssen immer
> paarweise auftreten, es wurde aber ein Teil ohne
> Entsprechung gefunden (siehe rote Markierung)
>
> | 2*(Anzahl von a in w) = 3*(Anzahl von b in w)}
> ich definierte mein w dann so:
>
> w = a^{3n}b^{2n} (s.d 2 \* Anzahl von a = 3 \* Anzahl von b
> ist)
>
> Dann müssten wegen |xy| \le n x und y lauter a's sein (wie
> du schon gesagt hast).
>
> Also ist
> x:= a^{j}, y:=a^{k}, dann z:= a^{2n}b^{2n} mit k>0, j \le
> 0 und k + j = n.
Das stimmt nicht. Es kann auch $k + j < n$ sein. Es muss nur $k > 0$ sein.
> \Rightarrow w_{i} = a^{j}(a^{k})^{i} a^{2n}b^{2n} =
> a^{3n+(i-1)k}b^{2n}.
>
> für i = 0: w_{0} = a^{3n-k}b^{2n} also nicht \in L.
> \Rightarrow L nicht regulär.
![[ok]](/images/smileys/ok.gif "[ok]")
(fuer jedes andere $i \neq 1$ auch  )
> Ist das so richtig? (Natürlich noch nicht richtig
> ausformuliert..)
Bis auf das was ich oben angemerkt hatte, ja!
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:05 So 12.12.2010 | | Autor: | Loko |
Vielen Dank für die super schnelle Hilfe :)
Dann is alles klar!
|
|
|
|
