reguläre sprachen < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 20:06 Di 30.12.2008 | | Autor: | tugba |
| Aufgabe | zeigen Sie, dass die Sprache
[mm] L:=\{b^{k}a^{l}b^{l}|k\ge1,l\ge0\}\cup\{a^{k}b^{l}|k,l\ge0\}
[/mm]
nicht regulär ist. |
Ich verstehe hier die Lösung nicht, kann mir jemand den Lösung etwas verstendlicher ausdrücken.
Ich habe als Lösung:
[mm] M=\{a^{k}b^{l}|k,l\ge0\} [/mm] ist sicher regulär,da man hierfür einen endlichen Automaten angeben kann. ( Warum ist diese Sprache den regulär, ich weiss, dass zum Beispiel die Sprache [mm] \{a^{k}b^{l}|k,l\ge0\} [/mm] nicht regulär ist, und wie kann hier der endliche Automat aussehen.)
Falls L regulär wäre, wäre es auch [mm] L\M=\{b^{k}a^{l}b^{l}|k\ge1,l\ge0\}.Dies [/mm] ist aber nicht der Fall (Warum ist diese Sprache denn nicht regulär).
liebe grüße....
|
|
| |
|
Also erst einmal:
Reguläre Sprachen sind abgeschlossen unter Vereinigung. Warum? Nun, erstelle aus zwei DEA einen NEA mit den 2 Startzuständen von den DEA's.
Nun folgt der typische Widerspruchsbeweis. Angenommen, L wäre regulär, dann wäre auch jede der Vereinigungsmengen regulär. Das trifft bei [mm] \{a^{k}b^{l}|k,l\ge0\} [/mm] zu. Du musst nicht über den Automaten argumentieren, welcher einfach anzugeben wäre (hier eine informelle Beschreibung):
Startzustände = Endzustände = [mm] \{z_{0},z_{1}\}
[/mm]
dann
[mm] (z_{0}, [/mm] a) = [mm] z_{1}
[/mm]
[mm] (z_{0}, [/mm] a) = [mm] z_{0} [/mm]
[mm] (z_{1}, [/mm] b) = [mm] z_{1}
[/mm]
Du kannst auch über die Representation regulärer Sprachen durch reguläre Ausdrücke argumentieren, hier wäre a*b* der äquivalente Ausdruck.
So, jetzt folgt die zweite Vereinigungsmenge [mm] \{b^{k}a^{l}b^{l}|k\ge1,l\ge0\}\ [/mm]
Auch hier kannst du verschieden argumentieren. Du kannst das Pumping-Lemma anwenden. Oder du kannst wieder über die Abschlusseigenschaften gehen.
[mm] \{b^{k}a^{l}b^{l}|k\ge1,l\ge0\}\ [/mm] lässt sich auch als [mm] \{b^{k}|k\ge1\}\ \times \{a^{l}b^{l}|l\ge0\}\ [/mm] schreiben.
Da reguläre Sprachen auch unter Kreuzprodukt (da lässt sich ebenfalls ein Automat konstruieren..) abgeschlossen sind und [mm] \{a^{l}b^{l}|l\ge0\}\ [/mm] bekanntermaßen kontextfrei ist, folgt dass [mm] \{b^{k}a^{l}b^{l}|k\ge1,l\ge0\}\ [/mm] nicht regulär sein kann und damit auch L nicht.
Ich hoffe du konntest allem folgen.
|
|
|
|
