Pumping-Lemma < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Beweisen oder widerlegen Sie mit dem Pumping-Lemma, dass die folgende Sprache regulär ist:
[mm] $L_1 [/mm] = [mm] \{ 0^j1^k0^l | j=k+l \text{ für }j,k,l \in \mathbb N \}$ [/mm] |
So, dann fang ich nochmal an:
Vermutung: L ist regulär!
Sei [mm] $n_0$ [/mm] die Konstante des PL, dann gilt: [mm] $n_0 \in \mathbb [/mm] N$ mit [mm] $n_0 \geq [/mm] 1$:
$w = [mm] 0^{n_0}1^k0^l$
[/mm]
Für alle $w [mm] \in [/mm] L$ mit $|w| [mm] \geq n_0$ [/mm] mit $u,v,w [mm] \in \Sigma^{\star}_{\text{Bool}}$ [/mm] und $|uv| [mm] \leq [/mm] 1$ und $v [mm] \neq \epsilon$ [/mm] gilt die Zerlegung:
$w = [mm] \underbrace{0^{m_1}}_{\text{=u}} \underbrace{0^{m_2}}_{\text{=v}} \underbrace{1^k 0^l}_{\text{=w}}$ [/mm] mit [mm] $m_1+m_2=j$
[/mm]
Betrachte: $uv^iw [mm] \in [/mm] L$ mit i=2: $uv^2w = [mm] 0^{m_1}(0^{m_2})^21^k0^l [/mm] = [mm] 0^{m_1}0^{2m_2}1^k0^l [/mm] = ...?$
Und ab hier weiß ich dann nicht mehr weiter. Laut der Sprachdefinition von oben hängt die Anzahl der ersten Nulln [mm] $0^j$ [/mm] von der Anzahl der Zeichen [mm] $1^k$ [/mm] und [mm] $0^l$ [/mm] ab. Wenn ich jetzt bspw. k=2 und l=3 wähle, dann berechnet sich ja j=k+l=5. Dann sieht das Wort w ja so aus: 0000011000.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:20 Do 17.05.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:41 Mo 21.05.2012 | | Autor: | sandp |
hey,
Mit dem PL kann man nur zeigen, dass eine Sprache nicht regulär ist, die andere Richtung funktioniert nicht.
Um zu zeigen, dass eine Sprache regulär ist kannst du ja zum Beispiel eine Grammatik dafür angeben.
Gruß
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:27 Do 24.05.2012 | | Autor: | bandchef |
Ja, das weiß ich. Genau deswegen hab ich ja in der Vermutung geschrieben, dass ich vermute, dass L regulär ist. Dann kommt beim PL-Beweis raus, dass es eben nicht regulär ist. Und dann hab ich das gegenteil Bewiesen.
Ist das so richtig?
|
|
|
|
