Pumping Lemma < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:19 Sa 27.04.2013 | | Autor: | bandchef |
| Aufgabe | Zeigen Sie mit Hilfe des Pumping-Lemmas für reguläre Sprachen, dass die folgende Sprache nicht regulär ist:
$L = [mm] \{ a^k b^l | k,l \in \mathbb N, 20 \leq k+l \leq 40 \}$ [/mm] |
Hi Leute!
Ich hab nun versucht mit dem Pumping Lemma ein Gegenbeispiel zu finden, dass die Sprache nicht regulär ist.
Sei L eine reguläre Sprache, dann gibt es eine Konstante $n [mm] \in \mathbb [/mm] N$ so dass sich jedes $z [mm] \in [/mm] L$ mit $|z| [mm] \geq [/mm] n$, so als $z=uvw$ schreiben lässt, dass $|uv| [mm] \leq [/mm] n$, $|v| [mm] \geq [/mm] 1$ und $uv^iw [mm] \in [/mm] L$ mit $i [mm] \geq [/mm] 0$ gilt.
Ich wähle: $z = [mm] a^{20n}b^{20n} \in [/mm] L$, $|z| [mm] \geq 2\cdot [/mm] 20n$
20n | 20n
a.....a|b.....b
uv | w
So gilt: $uv^iw = uv^2w [mm] \notin [/mm] L$, und somit auch nicht regulär da so nun mindestens ein a zu viel ist.
Stimmt das so?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:01 Sa 27.04.2013 | | Autor: | tobit09 |
Hallo bandchef,
> Zeigen Sie mit Hilfe des Pumping-Lemmas für reguläre
> Sprachen, dass die folgende Sprache nicht regulär ist:
>
> [mm]L = \{ a^k b^l | k,l \in \mathbb N, 20 \leq k+l \leq 40 \}[/mm]
Das wird dir nicht gelingen; diese Sprache ist nämlich endlich und somit regulär!
> Ich hab nun versucht mit dem Pumping Lemma ein
> Gegenbeispiel zu finden, dass die Sprache nicht regulär
> ist.
>
>
>
> Sei L eine reguläre Sprache, dann gibt es eine Konstante [mm]n \in \mathbb N[/mm]
> so dass sich jedes [mm]z \in L[/mm] mit [mm]|z| \geq n[/mm], so als [mm]z=uvw[/mm]
> schreiben lässt, dass [mm]|uv| \leq n[/mm],
[mm]|v| \geq 1[/mm] und [mm]uv^iw \in L[/mm]
> mit [mm]i \geq 0[/mm] gilt.
Was heißt "mit [mm] $i\geq [/mm] 0$ gelten"? Die Aussage ist, dass dies für ALLE [mm] $i\geq [/mm] 0$ gilt.
> Ich wähle: [mm]z = a^{20n}b^{20n} \in L[/mm], [mm]|z| \geq 2\cdot 20n[/mm]
Du musst erklären, was du mit $n$ meinst. Vermutlich willst du folgendermaßen argumentieren: Wäre $L$ regulär, gäbe es ein [mm] $n\in\IN$ [/mm] mit der Eigenschaft wie im Pumping Lemma formuliert.
Warum sollte nun [mm] $a^{20n}b^{20n}\in [/mm] L$ gelten? Dazu müsste nach Definition von $L$ schon [mm] $20n+20n\le40$ [/mm] sein, was nur für [mm] $n\le [/mm] 1$ der Fall ist.
> 20n | 20n
> a.....a|b.....b
> uv | w
>
> So gilt: [mm]uv^iw = uv^2w \notin L[/mm], und somit auch nicht
> regulär da so nun mindestens ein a zu viel ist.
Viele Grüße
Tobias
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:07 So 28.04.2013 | | Autor: | bandchef |
> Das wird dir nicht gelingen; diese Sprache ist nämlich endlich und somit regulär!
Hm, ich denke, dann hab ich wohl das Ziel der Aufgabe verfehlt. Man sollte wohl herausfinden, dass diese Sprache regulär ist und das somit mit dem PL nicht widerlegen kann.
> Warum sollte nun [mm] $a^{20n}b^{20n}\in [/mm] L$ gelten? Dazu müsste nach Definition von $L$ schon [mm] $20n+20n\le40$ [/mm] sein, was nur für [mm] $n\le [/mm] 1$ der Fall ist.
Dieses $20n + 20n$ ist doch quasi mein $|uv|$ aus $|uv| [mm] \leq [/mm] n$, oder?
Woher weiß ich, dass ich das so betrachten muss? Wenn ich nun n=5 setze, ist das Teilwort uv größer dem n. Ich muss aber eine Aufteilung finden, die bei jedem n rausfliegt. Richtig? Ich habe verstanden, dass die Sprache hier regulär ist und ich somit das mit dem PL nicht widerlegen kann. Aber ich habe doch hier nun gezeigt, dass ich mit n=2 hier aus der Sprache rausfliege. Wo ist dann hier der Fehler?
Dann kommt die nächste Frage auf: Woher weißt du, dass ich bei $|uv| [mm] \leq [/mm] n$ das n=40 setzen muss? Das der Wert 40 aus der Angabe kommt ist klar, aber woher weißt du, dass dieser Wert gleich dem n ist?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 13:23 Mo 29.04.2013 | | Autor: | tobit09 |
> > Warum sollte nun [mm]a^{20n}b^{20n}\in L[/mm] gelten? Dazu müsste
> nach Definition von [mm]L[/mm] schon [mm]20n+20n\le40[/mm] sein, was nur für
> [mm]n\le 1[/mm] der Fall ist.
>
> Dieses [mm]20n + 20n[/mm] ist doch quasi mein [mm]|uv|[/mm] aus [mm]|uv| \leq n[/mm],
> oder?
Nein.
> Woher weiß ich, dass ich das so betrachten muss?
Du hast [mm] $a^{20n}b^{20n}\in [/mm] L$ behauptet. Nun ist
[mm] $L=\{a^kb^l\;|\;k,l\in\IN, 20\le k+l\le40\}$.
[/mm]
Damit [mm] $a^{20n}b^{20n}$ [/mm] wirklich ein Element von $L$ wäre, müsste schon [mm] $20\le k+l\le [/mm] 40$ für $k:=20n$ und $l:=20n$ gelten, also [mm] $20\le 20n+20n\le [/mm] 40$. Das gilt aber nur für $n=1$.
Du versuchst zu zeigen, dass die Bedingung aus dem Pumping Lemma verletzt ist. Nimm also an, dass die Bedingung aus dem Pumping Lemma gilt und führe das zu einem Widerspruch (was natürlich in diesem Beispiel nicht geht, da $L$ ja regulär ist).
> Wenn ich
> nun n=5 setze,
Wenn die Bedingung aus dem Pumping Lemma gilt, gibt es ein [mm] $n\in\IN$ [/mm] wie in der Bedingung des Pumping Lemmas. Dieses $n$ darfst du dir nicht aussuchen. Schließlich gilt die Bedingung aus dem Pumping Lemma nicht für alle [mm] $n\in\IN$, [/mm] sondern nur mindestens für ein $n$.
(Tatsächlich gilt es dann auch für alle größeren $n$, aber das kann dir egal sein. Vielleicht hilft es aber deiner Vorstellung, dir dieses $n$ als "sehr groß" vorzustellen.)
Das $n$ hat nun die Eigenschaft, dass für alle [mm] $z\in [/mm] L$ mit [mm] $|z|\ge [/mm] n$ eine gewisse Aussage (*) gilt.
Um das auszunutzen, kannst du ein von dir gewähltes Wort [mm] $z\in [/mm] L$ mit [mm] $|z|\ge [/mm] n$ hernehmen. (*) gilt also insbesondere für dieses $z$.
(Problem in diesem konkreten Beispiel: Die Wörter in $L$ haben alle Länge [mm] $\le40$. [/mm] Somit finden wir im Falle $n>40$ gar kein Wort [mm] $z\in [/mm] L$ mit [mm] $|z|\ge [/mm] n$.)
> ist das Teilwort uv größer dem n.
Teilwort welchen Wortes?
> Ich muss
> aber eine Aufteilung finden, die bei jedem n rausfliegt.
> Richtig?
Wenn du ein [mm] $z\in [/mm] L$ mit [mm] $|z|\ge [/mm] n$ gewählt hättest, würde die Bedingung (*) für $z$ aussagen:
Es gibt eine Aufteilung $z=uvw$ mit [mm] $|uv|\le [/mm] n$ und [mm] $|v|\ge [/mm] 1$, so dass [mm] $uv^iw\in [/mm] L$ für alle [mm] $i\in\IN$.
[/mm]
Du müsstest keine solche Aufteilung finden, sondern du hättest eine solche Aufteilung.
Das würde es nun zum Widerspruch zu führen gelten.
> Ich habe verstanden, dass die Sprache hier
> regulär ist und ich somit das mit dem PL nicht widerlegen
> kann. Aber ich habe doch hier nun gezeigt, dass ich mit n=2
> hier aus der Sprache rausfliege. Wo ist dann hier der
> Fehler?
Für $n=2$ gilt die Bedingung aus dem Pumping Lemma eben nicht. Aber das Pumping Lemma sagt ja auch nur, dass es im Falle der Regularität von $n$ IRGENDEINE Zahl $n$ gibt, über die etwas ausgesagt wird.
> Dann kommt die nächste Frage auf: Woher weißt du, dass
> ich bei [mm]|uv| \leq n[/mm] das n=40 setzen muss?
> Das der Wert 40
> aus der Angabe kommt ist klar, aber woher weißt du, dass
> dieser Wert gleich dem n ist?
Nein, ich habe nirgendwo irgendein $n$ auf 40 gesetzt.
Ich weiß gerade nicht, ob ich das Folgende schon mal gefragt habe: Ist die 0 bei euch eigentlich eine natürliche Zahl oder nicht?
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:08 Mo 29.04.2013 | | Autor: | bandchef |
Es tut mir sehr leid, aber ich kann dir irgendwie hier nicht folgen. Das die Aufgabe hier regulär ist, weiß ich ja jetzt weil du es gesagt hast. Somit kann ich mit dem PL auch nix widerlegen.
Aber was muss ich hier nun hinschreiben, damit ich zeigen kann, dass ich hier mit dem PL nix widerlegen kann? Es reicht also ein n zu finden, das passt, oder?
Was ist nun wenn ich so wähle:
[mm] $z=a^{10n}b^{10n}$ [/mm] Hier liege ich nun mit n=1 und n=2 im Intervall, das durch die Aufgabe gegeben ist!
$z=uv^iw=uv^2w [mm] \in [/mm] L$
Hierfür muss man doch jetzt irgendwie eine Zeichnung machen können, oder? Ich hab bei solchen Aufgaben immer das Probleme, das sich es mir nicht vorstellen kann! Ich muss da ja irgendwie den a-Teil des Wortes in ein u und v aufteilen und den b-Teil in das w!
Wenn ich nun ab irgendeinem a im a-Teil des Wortes das v mit "hoch 2" aufpumpe, bekomme ich ja dann mehr a's als b's, oder?
Aber ich weiß ja dann noch lange nicht, ob ich mit [mm] $v^2$ [/mm] dann nicht ein längeres Wort als 40 Zeichen bekomme!
Da ich aber weiß, dass ich ja angeblich mein v gar nicht falsch wählen kann, weil die Sprache ja eh regulär ist, kapier ich's gleich dreimal nicht.
Ich weiß ehrlich gesagt auch gar nicht mehr wie ich mein Problem mit solchen Aufgaben (nicht nur speziell bei dieser Aufgabe wo man ja das PL auf eine reguläre Sprache anwenden soll, sondern GENERELL!) schildern soll! Es fehlt mir einfach das Wissen, die Vorstellungskraft.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:49 Mo 29.04.2013 | | Autor: | tobit09 |
> Es tut mir sehr leid, aber ich kann dir irgendwie hier
> nicht folgen. Das die Aufgabe hier regulär ist, weiß ich
> ja jetzt weil du es gesagt hast. Somit kann ich mit dem PL
> auch nix widerlegen.
Stimmt. Ich wollte dir nur erklären, was du tun müsstest, wenn du mittels Pumping Lemma die Regularität widerlegen wolltest (was du natürlich nicht kannst). Sorry für die Verwirrung, die ich damit ausgelöst habe.
> Aber was muss ich hier nun hinschreiben, damit ich zeigen
> kann, dass ich hier mit dem PL nix widerlegen kann?
Du möchtest also nun zeigen, dass die Bedingung "es gibt ein [mm] $n\in\IN$, [/mm] sodass ..." aus dem Pumping Lemma für unser $L$ erfüllt ist? (Vorsicht: Daraus folgt noch nicht, dass die Sprache regulär ist.) Oder möchtest du die Regularität beweisen? Ich gehe jetzt erst einmal von ersterem aus.
> Es
> reicht also ein n zu finden, das passt, oder?
Ja.
Wähle z.B. $n=10000000000000$ oder $n=41$.
Die Aussage zu beweisende Aussage aus dem Pumping Lemma ist nun, dass für alle Wörter [mm] $z\in [/mm] L$, deren Länge [mm] $\ge [/mm] n$ ist etwas gilt.
Alle Wörter [mm] $z\in [/mm] L$ haben aber Länge [mm] $\le [/mm] 40$. Also gibt es gar keine Wörter [mm] $z\in [/mm] L$ der Länge [mm] $\ge [/mm] n$.
Also ist für die zu beweisende Aussage gar nichts weiter zu tun!
> Was ist nun wenn ich so wähle:
>
> [mm]z=a^{10n}b^{10n}[/mm]
Du wolltest doch korrekterweise ein $n$ wählen, das passt. Nun wählst du aber fälschlicherweise $z$!
> Hier liege ich nun mit n=1 und n=2 im
> Intervall, das durch die Aufgabe gegeben ist!
>
> [mm]z=uv^iw=uv^2w \in L[/mm]
>
> Hierfür muss man doch jetzt irgendwie eine Zeichnung
> machen können, oder? Ich hab bei solchen Aufgaben immer
> das Probleme, das sich es mir nicht vorstellen kann! Ich
> muss da ja irgendwie den a-Teil des Wortes in ein u und v
> aufteilen und den b-Teil in das w!
>
> Wenn ich nun ab irgendeinem a im a-Teil des Wortes das v
> mit "hoch 2" aufpumpe, bekomme ich ja dann mehr a's als
> b's, oder?
> Aber ich weiß ja dann noch lange nicht, ob ich mit [mm]v^2[/mm]
> dann nicht ein längeres Wort als 40 Zeichen bekomme!
Du hast quasi bewiesen, dass $n=1$ und $n=2$ nicht der Bedingung aus dem Pumping Lemma genügen.
$n=41$ beispielsweise genügt jedoch sehr wohl dieser Bedingung.
> Da ich aber weiß, dass ich ja angeblich mein v gar nicht
> falsch wählen kann, weil die Sprache ja eh regulär ist,
> kapier ich's gleich dreimal nicht.
(Wenn du nachweisen willst, dass die Bedingung aus dem Pumping Lemma gilt, kannst du sehr wohl eine falsche Wahl von $v$ treffen, obwohl es ein passendes $v$ gibt.)
> Ich weiß ehrlich gesagt auch gar nicht mehr wie ich mein
> Problem mit solchen Aufgaben (nicht nur speziell bei dieser
> Aufgabe wo man ja das PL auf eine reguläre Sprache
> anwenden soll, sondern GENERELL!) schildern soll! Es fehlt
> mir einfach das Wissen, die Vorstellungskraft.
Das Pumping Lemma ist ja auch nicht ganz einfach mit den vielen Quantoren.
Wichtig ist, dass du dir klar machst, was du jeweils selbst wählen darfst und welche Objekte du als gegeben hinnehmen muss.
Das hängt davon ab, ob es um einen [mm] $\exists$- [/mm] oder eine [mm] $\forall$-Quantor [/mm] geht, und ob du die Aussage zeigen möchtest, oder vorausgesetzt hast.
Wenn [mm] $\exists [/mm] x A(x)$ vorausgesetzt ist, musst du $x$ als gegeben hinnehmen.
Wenn [mm] $\forall [/mm] x A(x)$ vorausgesetzt ist, kannst du selbst ein $x$ wählen und für dieses gilt zwangsläufig die Bedingung $A(x)$.
Wenn du [mm] $\exists [/mm] x A(x)$ zeigen willst, kannst du dir selbst aussuchen, für welches $x$ du $A(x)$ zeigen möchtest (wobei dir das natürlich i.A. nicht für jedes $x$ gelingen wird).
Wenn du [mm] $\forall [/mm] x A(x)$ zeigen möchtest, musst du ein $x$ als gegeben hinnehmen und für dieses $A(x)$ zeigen.
Also wenn du die Bedingung [mm] "$\exists n\in\IN\colon\ldots$" [/mm] aus dem Pumping Lemma ZEIGEN möchtest, darfst du zwar selbst $n$ wählen, kannst aber eine falsche Wahl treffen.
Wenn du dagegen die Bedingung [mm] "$\exists n\in\IN\colon\ldots$" [/mm] aus dem Pumping Lemma VORAUSSETZT, musst du mit einem beliebig vorgegebenen [mm] $n\in\IN$ [/mm] (das du nicht selbst wählen kannst) vorlieb nehmen.
Das ist etwa der Fall, wenn du zeigen willst, dass eine Sprache nicht regulär ist und widerspruchshalber annimmst, sie wäre regulär. Dann würde sie der Bedingung aus dem Pumping Lemma genügen. Also setzt du hier [mm] "$\exists n\in\IN\colon\ldots$" [/mm] voraus.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:12 Di 30.04.2013 | | Autor: | bandchef |
Aufgepasst 
Jetzt mach ich was ganz verrücktes: Ich ändere nun die gegebene Sprache ab: $ L = [mm] \{ a^k b^l | k,l \in \mathbb N, 20 \leq k-l \leq 40 \} [/mm] $
Laut unserem Prof. ist nun die Sprache nicht mehr regulär.
Ich beginne nun wieder:
Sei L regulär, dann existiert ein $n [mm] \in \mathbb [/mm] N$ mit der Eigenschaft: Jedes Wort $z [mm] \in [/mm] L$ mit [mm] $|z|\geq [/mm] n$ lässt sich zerlegen in uvw mit: $|v| [mm] \geq [/mm] 1$, |uv| [mm] \leq [/mm] n und $uv^iw [mm] \in [/mm] L$ für [mm] $i\geq [/mm] 0$.
[mm] $z=a^{n+20}b^n$
[/mm]
An dieser Stelle muss ich ja nun prüfen, ob das gewählte Wort in der Sprache liegt: $n+20-n=20 [mm] \underbrace{\geq 20}_{\text{Welche Bedingung ist das? \\ Ist das die Bedingung aus der Sprache, \\ dass ein korrektes Wort größergleich 20 sein muss?}}$
[/mm]
d.h.: $z [mm] \in [/mm] L$, $|z|=2n+20 [mm] \geq [/mm] n$
Wenn man nun die Pump-Schleife in den a-Teil legt und ein a aus dem Wort abpumpt flieg ich aus der Sprache raus und es gilt: $uv^0w [mm] \notin [/mm] L$.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:03 Di 30.04.2013 | | Autor: | tobit09 |
> Aufgepasst
>
> Jetzt mach ich was ganz verrücktes: Ich ändere nun die
> gegebene Sprache ab: [mm]L = \{ a^k b^l | k,l \in \mathbb N, 20 \leq k-l \leq 40 \}[/mm]
>
> Laut unserem Prof. ist nun die Sprache nicht mehr
> regulär.
>
> Ich beginne nun wieder:
>
> Sei L regulär, dann existiert ein [mm]n \in \mathbb N[/mm] mit der
> Eigenschaft: Jedes Wort [mm]z \in L[/mm] mit [mm]|z|\geq n[/mm] lässt sich
> zerlegen in uvw mit: [mm]|v| \geq 1[/mm], |uv| [mm]\leq[/mm] n und [mm]uv^iw \in L[/mm]
> für [mm]i\geq 0[/mm].
Unterschlag doch nicht immer das "alle" bei "für ALLE [mm] $i\geq [/mm] 0$"!
> [mm]z=a^{n+20}b^n[/mm]
>
> An dieser Stelle muss ich ja nun prüfen, ob das gewählte
> Wort in der Sprache liegt: [mm]n+20-n=20 \underbrace{\geq 20}_{\text{Welche Bedingung ist das? \\ Ist das die Bedingung aus der Sprache, \\ dass ein korrektes Wort größergleich 20 sein muss?}}[/mm]
Nicht ein korrektes Wort muss größer gleich 20 sein, sondern die Anzahl der a's zu Beginn muss um mindestens 20 und höchstens 40 größer sein, als die Anzahl der b's am Ende.
> d.h.: [mm]z \in L[/mm], [mm]|z|=2n+20 \geq n[/mm]
Schön! ![[ok]](/images/smileys/ok.gif "[ok]")
> Wenn man nun die Pump-Schleife in den a-Teil legt
Den darfst du nicht selbst wählen. Sondern nach Wahl von $n$ gibt es eine Zerlegung $z=uvw$ mit [mm] $|v|\ge [/mm] 1$, [mm] $|uv|\le [/mm] n$ und [mm] $uv^iw\in [/mm] L$ für alle [mm] $i\ge [/mm] 0$.
Da uv ein Anfangsstück von [mm] $z=a^{n+20}b^n$ [/mm] der Länge [mm] $\le [/mm] n$ ist, besteht uv nur aus a's. Insbesondere besteht $v$ nur aus a's.
> und ein a
> aus dem Wort abpumpt flieg ich aus der Sprache raus und es
> gilt: [mm]uv^0w \notin L[/mm].
Ja. Es gilt [mm] $uv^0w=a^{n+20-|v|}b^n$ [/mm] und wegen [mm] $(n+20-\underbrace{|v|}_{\ge 1})-n\le [/mm] n+20-1-n=19<20$ folgt [mm] $uv^0w\notin [/mm] L$.
Dies widerspricht der Eigenschaft [mm] $uv^iw\in [/mm] L$ für alle [mm] $i\ge0$. [/mm] Also muss unsere Annahme, dass $L$ regulär sei, falsch gewesen sein. $L$ ist also in der Tat nicht regulär.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:43 Do 02.05.2013 | | Autor: | tobit09 |
> > d.h.: [mm]z \in L[/mm], [mm]|z|=2n+20 \geq n[/mm]
> > Schön!
>
> Dass das hier stimmt ist klar, weil wir das ja an der Uni
> gemacht haben. ich weiß z.B. hier schon gleich mal nicht
> wie man auf 2n+20 kommt...
Du hattest [mm] $z=a^{n+20}b^n$ [/mm] gewählt. Dieses Wort besteht genau aus $n+20$ vielen a's und $n$ vielen b's. Also hat $z$ genau die Länge $(n+20)+n$.
> > Wenn man nun die Pump-Schleife in den a-Teil legt
> > Den darfst du nicht selbst wählen. Sondern nach Wahl von [mm]n[/mm]
> gibt es eine Zerlegung [mm]z=uvw[/mm] mit [mm]|v|\ge 1[/mm], [mm]|uv|\le n[/mm] und
> > [mm]uv^iw\in L[/mm] für alle [mm]i\ge 0[/mm].
>
> Das kapier ich nicht. Wie sehe ich das wo ich das |uv|
> legen muss. Das mach ich schon Monate falsch! Ich will das
> jetzt endlich wissen, wie ich das legen muss, bzw. wie ich
> das erkenne!!! 
Du sollst das $|uv|$ gar nicht selbst legen! Du musst vorlieb nehmen mit irgendeiner Aufteilung $z=uvw$, die dir vorgegeben wird. Nur [mm] $|uv|\le [/mm] n$, [mm] $|v|\ge [/mm] 1$ und [mm] $uv^iw\in [/mm] L$ für alle [mm] $i\in\IN_0$ [/mm] darfst du annehmen.
> > Da uv ein Anfangsstück von [mm]z=a^{n+20}b^n[/mm] der Länge [mm]\le n[/mm]
> ist, besteht uv nur aus a's. Insbesondere besteht [mm]v[/mm] nur aus
> a's.
>
> Gleiche Frage: Wie erkenne ich das?
[mm] $z=a^{n+20}b^n$ [/mm] fängt mit $n+20$ vielen a's an. Jedes Anfangsstück von $z$ der Länge [mm] $\le [/mm] n+20$ besteht also nur aus a's. Damit besteht insbesondere das Anfangsstück $uv$ von $z$ der Länge [mm] $\le n\le [/mm] n+20$ nur aus a's. Also bestehen $u$ und $v$ nur aus a's.
> > Ja. Es gilt [mm]uv^0w=a^{n+20-|v|}b^n[/mm] und wegen
> [mm](n+20-\underbrace{|v|}_{\ge 1})-n\le n+20-1-n=19<20[/mm] folgt
> [mm]uv^0w\notin L[/mm].
>
> Die Ungleichung wieder genauso: Ich verstehe es nicht.
> Liegt wohl auch daran weil ich den Teil vorher nicht
> verstanden hab...
Gehen wir es zunächst mal ganz unformal an: Wenn ich aus dem Wort [mm] $z=a^{n+20}b^n$ [/mm] ein Teilwort $v$ der Länge [mm] $|v|\ge [/mm] 1$ entferne, das nur aus a's besteht, erhalte ich ein Wort, dass nicht mehr in der Sprache $L$ liegt.
Das habe ich nun formal begründet. Wie sieht $uv^0w$ (das ist so ein Wort, dass aus $z$ durch Entfernen eines nur aus a's bestehenden Teilwortes der Länge [mm] $\ge1$ [/mm] entsteht) aus? Es "fehlen" in $uv^0w$ gegenüber $z$ eben $|v|$ viele a's. Statt $n+20$ vielen a's (wie sie in [mm] $z=a^{n+20}b^n$ [/mm] vorkommen) hat $uv^0w$ nur noch $n+20-|v|$ viele a's. Ansonsten sehen $z$ und $uv^0w$ gleich aus. Also [mm] $uv^0w=a^{n+20-|v|}b^n$.
[/mm]
Liegt $uv^0w$ in $L$? Dazu müssen wir nach Definition von $L$ überprüfen, ob $k:=n+20-|v|$ und $l:=n$ die Ungleichungen [mm] $20\le k-l\le [/mm] 40$ erfüllen. Meine Behauptung war nun, dass die Ungleichung [mm] $20\le [/mm] k-l$ verletzt ist. Rechnen wir es nach:
$k-l=(n+20-|v|)-n=20-|v|<20$
Das $<$-Zeichen gilt, da [mm] $|v|\ge [/mm] 1$.
Also tatsächlich [mm] $uv^0w\notin [/mm] L$ entgegen der Wahl der Aufteilung $z=uvw$ mit [mm] $uv^iw\in [/mm] L$ für alle [mm] $i\in\IN_0$, [/mm] Widerspruch. Also war unsere Annahme, dass $L$ regulär sei, falsch.
|
|
|
|
