Pumping-Lemma, Myhill-Nerode < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe 1 | Gegeneb sein das Alphabet [mm] \summe [/mm] = {a,b}, das unendlich lange Wort [mm] w_\infty [/mm] über [mm] \summe [/mm] mit
w_infty = [mm] aba^2ba^3ba^4b...ba^nba^{n+1}b...
[/mm]
und die Sprache L [mm] \subset \summe [/mm] * bestehend aus der Menge aller Präfixe des Wortes [mm] w_\infty.
[/mm]
Beweisen Sie mit Hilfe des Pumping Lemms, dass L nicht regulär ist. |
| Aufgabe 2 | Zeigen Sie mit dem Myhill-Nerode-Kriterium, dass die folgenden Sprachen über [mm] \summe [/mm] = {0,1} regulär sind Konstruieren Sie jeweils den minimal Automat.
a. L={0w | w [mm] \in \summe [/mm] *}
b. L={w0 | w [mm] \in \summe [/mm] *} |
| Aufgabe 3 | Seien R,N,E Sprachen über [mm] \summe. [/mm] Sei R regulär, N nicht regulär und E endlich. Welche der folgenden Aussagen ist wahr?. Begründen sie Ihre Anwort.
a. R - E ist regulär
b. N - E ist nicht regulär.
c. N - R ist nicht regulär. |
Miau
ich hoffe man kann mir bei diesen Aufgaben helfen
zur ersten Aufgabe
ich habe jetzt für die Pumping Lemmazahl n gewählt und
x= [mm] aba^2ba^3ba^4b...ba^{n-1}ba^nb
[/mm]
für v wähle ich das erste a, damit |uv| [mm] \le [/mm] n ist
und man sieht ja dann, dass [mm] a^iba^2ba^3ba^4b...ba^{n-1}ba^nb [/mm] nicht in L ist, weil es kein Präfix ist
finde diese Lösung allerdings zu einfach und bin deshalb sehr davon überzeugt, dass sie falsch ist
zur zweiten aufgabe
zu zeigen ist ja, dass die Anzahl der Äquivalenzklassen endlich sind
a)
habe ich die Äquivalenzklassen
[0] = {x| x fängt mit 0 an}
[mm] [\epsilon] [/mm] ={x| x fängt nicht mit 0 an}
problem hier: ich weiß nicht so wirklich wie ich die Äquivalenzklassen bestimmen kann
und irgendwie fehlt mir noch eine, weil ich mit zwei Zuständen den DFA nicht zeichnen kann
b)
[mm] [\epsilon] [/mm] = {x| x endet nicht mit 0}
[0] = {x| x endet mit 0}
hier denke ich, dass es stimmt, weil ich einen DFA hinbekommen habe
zur dritten Aufgabe
habe mich noch nicht richtig damit beschäftigt, weil ich nicht weiß, was man mit R-E, N-E und N-R gemeint ist
wäre nett wenn mir das jemand sagen könnte
Miau :3
Katze
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 20:17 Sa 14.05.2011 | | Autor: | felixf |
Miau!
> Seien R,N,E Sprachen über [mm]\summe.[/mm] Sei R regulär, N nicht
> regulär und E endlich. Welche der folgenden Aussagen ist
> wahr?. Begründen sie Ihre Anwort.
> a. R - E ist regulär
> b. N - E ist nicht regulär.
> c. N - R ist nicht regulär.
>
> zur dritten Aufgabe
> habe mich noch nicht richtig damit beschäftigt, weil ich
> nicht weiß, was man mit R-E, N-E und N-R gemeint ist
> wäre nett wenn mir das jemand sagen könnte
Damit ist wohl die mengentheoretische Differenz gemeint: $A - B$ ist die Menge der Elemente, die in $A$ liegt aber nicht in $B$. Oft schreibt man dafuer $A [mm] \setminus [/mm] B$, manchmal aber auch $A - B$.
(Da $A + B$ und $A - B$ fuer Teilmengen $A, B$ einer additiv geschriebenen Gruppe eine andere Bedeutung hat sollte man besser $A [mm] \setminus [/mm] B$ anstelle $A - B$ fuer die mengentheoretische Differenz schreiben.)
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 22:42 Sa 14.05.2011 | | Autor: | Katze_91 |
okay danke
mit was beweist man das?
würde jetzt sagen
a) ist wahr, weil ich von der Sprache nur Wörter "abziehe" und so eigentlich den sprachen typ gehalte oder?
aber dann hat die Sprache eine neue Grammatik, die theoretisch ja dann auch nicht nur regulär sein kann
ausser ist füge dann in die Produktionen noch ein, dass die Produktionen, die zu den Wörten, die in E sind nach [mm] \epsilon [/mm] gehen....
also finde ich doch wieder eine reguläre Sprache, weil ich ja mit der Epsilonsonderregelung eine Epsilonfreie Grammatik finden kann
b) ist auch wieder war, gleiche Begründung wie bei a)
kann man das so sagen?
miau :3
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 22:50 Sa 14.05.2011 | | Autor: | felixf |
Miau!
> okay danke
> mit was beweist man das?
Mit solchen Saetzen wie "Sind $A$ und $B$ regulaer, so auch $A [mm] \cup [/mm] B$, $A [mm] \cap [/mm] B$, ..."
Oder halt mit Gegenbeispielen.
Die Sprache [mm] $\emptyset$ [/mm] ist z.B. endlich (und auch regulaer), die Sprache [mm] $\Sigma^\ast$ [/mm] ist nicht endlich, aber regulaer.
> würde jetzt sagen
> a) ist wahr, weil ich von der Sprache nur Wörter
> "abziehe" und so eigentlich den sprachen typ gehalte oder?
Nicht umbedingt. Du musst das schon formal korrekt begruenden.
Du kannst $A [mm] \setminus [/mm] B$ uebrigens auch schreiben als $A [mm] \cap (\Sigma^\ast \setminus [/mm] B)$.
> aber dann hat die Sprache eine neue Grammatik, die
> theoretisch ja dann auch nicht nur regulär sein kann
>
> ausser ist füge dann in die Produktionen noch ein, dass
> die Produktionen, die zu den Wörten, die in E sind nach
> [mm]\epsilon[/mm] gehen....
Ich wuerd hier nicht ueber Grammatiken nachdenken. Den Schnitt oder Vereinigung oder Differenz von Sprachen ueber Grammatiken anzuschauen bringt normalerweise nichts.
> also finde ich doch wieder eine reguläre Sprache, weil
> ich ja mit der Epsilonsonderregelung eine Epsilonfreie
> Grammatik finden kann
>
> b) ist auch wieder war, gleiche Begründung wie bei a)
Es ist wahr, aber die Begruendung funktioniert hier ebensowenig.
LG Felix
|
|
|
| |
|
miau
habe jetzt ein bisschen an den Aufgaben gearbeitet und bin jetzt schon mal viel weiter, vielen Dank
c folgt ja gerade aus b
weil jede endliche Sprache nach dem Myhill- ....-Satz ja regulär ist
aber bei der b komme ich gerade nicht weiter
ich war ja der Meinung, dass die aussage richtig ist
also N-E nicht regulär ist
kann ich das so beweisen?
N-E = [mm] N\cap (\Sigma^\ast \setminus [/mm] E ) = [mm] N\cap\overline{E} [/mm]
dann kann ich ja mal behaupten, dass die regulär wären fände da aber ein Gegenbeispiel
Sei N eine beliebige nicht reguläre Sprache und [mm] \overline{E} [/mm] = [mm] \Sigma^\ast
[/mm]
also E= [mm] \emptyset
[/mm]
N [mm] \cap \Sigma^\ast [/mm] = N und die ist nicht regulär....
wäre das so okay oder bin ich hier zu speziell?
wäre lieb wenn mir noch einer antworten würde, ich weiß ich bin ziemlich spät dran
LG Katze :3
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 02:20 Mi 18.05.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:20 Sa 14.05.2011 | | Autor: | felixf |
Miau!
> Gegeneb sein das Alphabet [mm]\summe[/mm] = {a,b}, das unendlich
> lange Wort [mm]w_\infty[/mm] über [mm]\summe[/mm] mit
> w_infty = [mm]aba^2ba^3ba^4b...ba^nba^{n+1}b...[/mm]
> und die Sprache L [mm]\subset \summe[/mm] * bestehend aus der Menge
> aller Präfixe des Wortes [mm]w_\infty.[/mm]
> Beweisen Sie mit Hilfe des Pumping Lemms, dass L nicht
> regulär ist.
> zur ersten Aufgabe
> ich habe jetzt für die Pumping Lemmazahl n gewählt und
> x= [mm]aba^2ba^3ba^4b...ba^{n-1}ba^nb[/mm]
Soweit ok.
> für v wähle ich das erste a, damit |uv| [mm]\le[/mm] n ist
Du kannst dir $v$ nicht aussuchen. Du weisst nur, dass es eine Zerlegung gibt mit $|u v| [mm] \le [/mm] n$.
Damit musst du dann arbeiten. (Beachte: wieviele Woerter gibt es in $L$, die mit $b [mm] a^n [/mm] b$ aufhoeren?)
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 22:14 Sa 14.05.2011 | | Autor: | Katze_91 |
miau :3
also wenn ich die Definition von Präfixen richtig verstanden habe, dann gibt es nur ein Wort in L, das mit ba^nb endet
heißt ja dann, dass wenn ich im wort im vorderen teil was änder, dass es dann nicht mehr in der Sprache ist?
habe irgendwie ein Problem damit abzugrenzen wo uv ist, wegen der a's die so schnell so viele werden.
Liebe Grüße
Katze
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 22:38 Sa 14.05.2011 | | Autor: | felixf |
Miau! =^.^=
> also wenn ich die Definition von Präfixen richtig
> verstanden habe, dann gibt es nur ein Wort in L, das mit
> ba^nb endet
![[ok]](/images/smileys/ok.gif "[ok]")
> heißt ja dann, dass wenn ich im wort im vorderen teil was
> änder, dass es dann nicht mehr in der Sprache ist?
Genau.
> habe irgendwie ein Problem damit abzugrenzen wo uv ist,
> wegen der a's die so schnell so viele werden.
Nunja, du weisst dass $|u v| [mm] \le [/mm] n$ ist und dass $u v w = x = a b [mm] a^2 b^2 \cdots a^{n-1} b^{n-1} a^n b^n$; [/mm] dieses Wort hat die Laenge $2 [mm] \sum_{k=1}^n [/mm] k = 2 [mm] \cdot \frac{n (n + 1)}{2} [/mm] = n (n + 1)$. Das heisst egal wie $u, v, w$ gewaehlt sind, $u [mm] v^\ell [/mm] w$ hoert immer mit $b [mm] a^n [/mm] b$ auf, da $w$ mindestens die Laenge $n + 2$ hat (solange $n$ nicht zuaellig 1 ist, aber du kannst ohne Einschraenkung $n$ als gross genug annehmen).
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:24 Mo 16.05.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
