Pumping Lemma < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Zeige mit Hilfe des Pumping-Lemma, dass die folgende Sprache nicht regulär ist
[mm] $L_1 [/mm] = [mm] \{x1^k: w \in \{0,1\}^{\*} \wedge |x| = k\}$ [/mm] |
Folgendes habe ich gemacht:
Sei [mm] $x1^k \in [/mm] L$ mit [mm] $|x1^k| [/mm] > n$. Dann muss $v = [mm] 1^k$ [/mm] mit $1 [mm] \le [/mm] k [mm] \le [/mm] n/2$ sein, da $v$ nicht leer sein darf und $|uv| [mm] \le [/mm] n$ sein muss. Dann ist [mm] $w=1^{|x|-k}$. [/mm] Da ist mit $i=0$ das Wort $uw = [mm] x1^{|x|-k} \not\in [/mm] L$.
Darf ich so argumentieren? Bin mir immernoch nicht sicher ob die Wahl von $n$ so gut war. Bin wir nicht sicher ob das mit $1 [mm] \le [/mm] k [mm] \le [/mm] n/2$ so geht.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:20 Sa 16.05.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
