Sprache überprüfen < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:27 Fr 03.06.2011 | | Autor: | bandchef |
| Aufgabe | Beweisen oder widerlegen Sie, dass die folgende Sprache regulär ist:
$L = [mm] \{ 0^n1^m | n \neq m \}$
[/mm]
Sie dürfen das Pumping-Lemma nicht verwenden. |
Wie fange ich da nun am besten an? Insebesondere weil man ja das Pumping-Lemma nicht verwenden darf.
Könnt ihr mir helfen?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 16:37 So 05.06.2011 | | Autor: | felixf |
Moin!
> Beweisen oder widerlegen Sie, dass die folgende Sprache
> regulär ist:
>
> [mm]L = \{ 0^n1^m | n \neq m \}[/mm]
>
> Sie dürfen das Pumping-Lemma nicht verwenden.
> Wie fange ich da nun am besten an? Insebesondere weil man
> ja das Pumping-Lemma nicht verwenden darf.
>
> Könnt ihr mir helfen?
Du kannst ja aenlich wie bei einer Idee eines Beweises des Pumping-Lemmas vorgehen.
Angenommen, der zugehoerige endliche deterministische Automat habe $n$ Zustaende. Betrachte das Wort [mm] $0^{n+1} 1^{((n+10)!)^2} \in [/mm] L$. Ueberlege dir jetzt, dass es $a, b [mm] \in \IN$ [/mm] geben muss mit $b, d > 0$, so dass $a + b = n + 1$ ist und [mm] $0^{a + k b} 1^{((n + 10)!)^2}$ [/mm] fuer jedes $k [mm] \in \IN$ [/mm] in $L$ liegt.
Finde nun $k$ mit $a + k b = ((n + [mm] 10)!)^2$. [/mm]
(Den Exponenten $((n + [mm] 10)!)^2$ [/mm] kannst du auch kleiner waehlen. Ueberleg dir mal, welches der kleinstmoeglichste Exponent ist, wenn du den Beweis fertig hast.)
LG Felix
|
|
|
|
