You are not logged in.

Spike

Trainee

  • "Spike" is male

Posts: 41

Date of registration: Nov 8th 2002

Location: Würzburg

41

Tuesday, February 11th 2003, 9:51am

Quoted

Original von Cipher

Aber ginge der Automat nicht noch einfacher?
so zum beispiel:

z0,a,# -> z0,A
z0,b,A -> z0,epsilon
z0,a,A -> z0,AA


Cipher



Ist z0 ein akzeptierender Zustand?

Nein: Dann würde dein Automat die leere Menge akzeptieren.

Ja: Dann würde dein Automat alle Wörter x akzeptieren, für die gilt: In allen Anfangsstücken von x kommen mehr a's als b's vor und in x selbst kommen mindestens so viele a's wie b's vor. Das Wort aababb würde z.B. akzeptiert werden, genauso wie das Wort aaa.

Wenn der Automat einmal begonnen hat, b's zu lesen, dürfen keine a's mehr kommen. Um das zu überprüfen, benötigt man mehr als einen Zustand. Deswegen glaube ich nicht, dass es einen kleineren Automaten gibt, als den zuerst angegebenen.

sr409

Junior Schreiberling

Posts: 156

Date of registration: Jan 3rd 2003

42

Tuesday, February 11th 2003, 10:48am

Quoted

Original von Joachim
Der NFA ist so in Ordnung, der DFA aber nicht:


Danke, hab's geupdatet. Hatte es falsch abhezeichnet - naja, war schon spät :)

Meine Aufgabe 4 sollte jetzt korrekt sein.

Cipher

Junior Schreiberling

  • "Cipher" is male

Posts: 156

Date of registration: Oct 15th 2002

Location: Berlin

Occupation: IT Application Consultant

43

Tuesday, February 11th 2003, 1:05pm

müssen wir in der klausur kellerautomaten mit endzuständen benutzen, oder reicht es als endzustand aus, wenn der keller leer ist?

im buch, dass ja als skript zur vorlesung verwendet wird, ist die definition eines kellers ja zunächst ohne endzustand (also, wird das wort durch leeren keller akzeptiert).

wurde in der vorlesung irgendwas festgelegt, oder ist das jedem selbst überlassen?

weil...(sorry, wenn ich mit der aufgabe nerve)...ohne Endzustand könnte doch Üb6 Aufg1 auch so aussehen, oder?

z0,a,# -> z0,A
z0,a,A -> z0,AA
z0,b,A -> z1,epsilon
z1,b,A -> z1,epsilon

Cipher

sr409

Junior Schreiberling

Posts: 156

Date of registration: Jan 3rd 2003

44

Tuesday, February 11th 2003, 1:10pm

Kann mir jemand nochmal das Pumping Lemma anhand von http://www-thi.informatik.uni-hannover.d…en/uebung05.pdf Aufgabe 1 erklären ?

Ich dachte ich hätte es kapiert...aber bei der Aufgabe weiß ich nicht so recht wie ich anfangen soll.

Thx.

  • "Joachim" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

45

Tuesday, February 11th 2003, 1:30pm

Quoted

Original von Cipher
ohne Endzustand könnte doch Üb6 Aufg1 auch so aussehen, oder?

z0,a,# -> z0,A
z0,a,A -> z0,AA
z0,b,A -> z1,epsilon
z1,b,A -> z1,epsilon
Prinzipiell schon, ist aber eigentlich nicht üblich.

Der bessere Weg wäre IMHO wirklich die Verwendung eines Endzustandes. Das macht das ganze auch lesbarer, da man sich nicht dauernd überlegen muß, wann der Stack denn nun leer sein könnte.
The purpose of computing is insight, not numbers.
Richard Hamming, 1962

Cipher

Junior Schreiberling

  • "Cipher" is male

Posts: 156

Date of registration: Oct 15th 2002

Location: Berlin

Occupation: IT Application Consultant

46

Tuesday, February 11th 2003, 2:10pm

Quoted

Original von sr409
Kann mir jemand nochmal das Pumping Lemma anhand von http://www-thi.informatik.uni-hannover.d…en/uebung05.pdf Aufgabe 1 erklären ?


Also, ich würde Üb5 A1 so lösen:

€ = element

Ich habe w (ein Wort aus der Sprache L in y umbenannt, damit es keine Verwechslung mit dem uvw aus dem Pumping Lemma gibt.

L = { yy^R | y € {a,b}* }


Pumping Lemma:

Es gibt eine Zahl n und ein Wort x=uvw mit |x|>=n.
Dann setze ich |y|=n und erhalte |x| = |yy^R| = |y|+|y|R = n+nR.

Wegen Bedingung 1 ( |v|>=1 ) kann v kein leeres Wort sein und wegen 2 ( |uv|<=n ) kann v nur aus Teilen von (/oder ganz aus) y bestehen.
Also: |uv|=|y|=n
Und wegen Bedingung 3 (es gibt ein i=0,1,2... : uv^iw € L) müsste für R=0 immer gelten:
uv^i € L. Und wenn ich speziell für i=0 einsetze, dann müsste u € L sein mit |u|<|uv|=|y|, wass im Widerspruch zur Defintion steht.

Hoffe, dass es richtig und nachvollziehbar ist.

Cipher

sr409

Junior Schreiberling

Posts: 156

Date of registration: Jan 3rd 2003

47

Tuesday, February 11th 2003, 2:21pm

Dieses hoch R bedeutet doch, dass das wort quasi invertiert ist ? Also:

x=abcd
x hoch R=dcba

korrekt ?

  • "Joachim" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

48

Tuesday, February 11th 2003, 2:22pm

Quoted

Original von sr409
Kann mir jemand nochmal das Pumping Lemma anhand von http://www-thi.informatik.uni-hannover.d…en/uebung05.pdf Aufgabe 1 erklären ?
Das folgende ist ohne Gewähr, das Pumping-Lemma habe ich das letzte Mal vor etwa einem Jahr benutzt und bin daher ein wenig aus der Übung. :)


L = {ww^R | w aus {a, b}^*}

Annahme: L ist regulär.

Dann muß L das Pumping-Lemma erfüllen, es gilt also:

Es gibt eine Zahl n, so daß für alle x aus L mit |x| >= n eine Zerlegung x = uvw existiert, für die die drei Bedingungen des Pumping-Lemma erfüllt sind.

Insbesondere gilt dies also auch für das Wort
x = a^(2n - 1) b b a^(2n - 1).

x hat offensichtlich die Länge 4n > n und muß daher die Bedingungen des Pumping-Lemmas erfüllen.

Nach diesen Bedingungen existiert eine Zerlegung x = uvw mit |v| >= 1 und |uv| <= n. Aufgrund der Struktur von x, besteht uv nur aus a's. Wir haben x also wie folgt zerlegt:

x = u v w = a^|u| a^|v| a^(2n - 1 - |u| - |v|) b b a^(2n - 1)

Nach dem Pumping-Lemma ist y = u v^0 w auch ein Wort der Sprache L. Es gilt:

y = u w = a^|u| a^(2n - 1 - |u| - |v|) b b a^(2n - 1)

Offensichtlich ist dies aber kein Wort aus L, da gilt
y = a^(2n - 1 - |v|) bb a^(2n - 1).
(2n - 1 - |v|) ist nämlich ungleich (2n - 1).

Daher muß die Annahme, daß L regulär ist, falsch sein.


Quoted

Dieses hoch R bedeutet doch, dass das wort quasi invertiert ist ? Also:

x=abcd
x hoch R=dcba

korrekt ?
Korrekt.
The purpose of computing is insight, not numbers.
Richard Hamming, 1962

sebi

Junior Schreiberling

  • "sebi" is male

Posts: 153

Date of registration: Dec 10th 2001

Location: Hannover, Erde

Occupation: lebenskünstler

49

Tuesday, February 11th 2003, 2:47pm

Quoted

x = a^(2n - 1) b b a^(2n - 1).


Wie kommst du da drauf ? ich tu mich immer an dieser stelle schwer, ein gutes beispiel zu raten ... vielleicht kannst du mir n tipp geben. thanks :)

Cipher

Junior Schreiberling

  • "Cipher" is male

Posts: 156

Date of registration: Oct 15th 2002

Location: Berlin

Occupation: IT Application Consultant

50

Tuesday, February 11th 2003, 2:50pm

ok, dann habe ich wohl hoch R falsch interpretiert....hmm..ärgerlich...

@Joachim:
und wie kommst du auf (2n-1) ? warum nimmst du nicht einfach nur n ?

Oh, da hat wohl schon einer vor mir die Frage gestellt... :)

  • "Joachim" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

51

Tuesday, February 11th 2003, 2:58pm

Quoted

Original von sebi

Quoted

x = a^(2n - 1) b b a^(2n - 1).


Wie kommst du da drauf ? ich tu mich immer an dieser stelle schwer, ein gutes beispiel zu raten ... vielleicht kannst du mir n tipp geben.
Tja, das ist eigentlich das Hauptproblem des Pumping-Lemmas. :)

Das Ziel ist es ja in der Regel, ein möglich einfaches v in der Zerlegung x = uvw zu haben, also ist es zweckmäßig, das Wort auch sehr einfach aufzubauen.

Mein Grundgedanke war, daß ich durch Entfernen oder Hinzufügen von a's im vorderen Teil des Wortes (also durch "Aufpumpen") die Mitte (also die beiden b's) verschieben wollte, um die Symmetrie des Wortes aufzuheben. Dann gehört es selbstverständlich nicht mehr zu L und das Pumping-Lemma ist verletzt.

Quoted

Original von cipher
@Joachim:
und wie kommst du auf (2n-1) ? warum nimmst du nicht einfach nur n ?
Ja, n hätte ich natürlich auch nehmen können. Danke für den Hinweis.
The purpose of computing is insight, not numbers.
Richard Hamming, 1962

sebi

Junior Schreiberling

  • "sebi" is male

Posts: 153

Date of registration: Dec 10th 2001

Location: Hannover, Erde

Occupation: lebenskünstler

52

Tuesday, February 11th 2003, 3:03pm

da du das ja lemminggleich aus dem ärmel zu pumpen scheinst, magst du das ganze nochmal mit 2n machen ? nur für mich & cipher zum verstehen ? merci beaucoup :) ich versteh das nämlich irgendwie nicht ganz...

  • "Joachim" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

53

Tuesday, February 11th 2003, 3:14pm

Quoted

Original von sebi
da du das ja lemminggleich aus dem ärmel zu pumpen scheinst, magst du das ganze nochmal mit 2n machen ? nur für mich & cipher zum verstehen ?
Ich mach's mal mit n. Ist eigentlich fast genau das selbe:


L = {zz^R | z aus {a, b}^*}

Annahme: L ist regulär.

Dann muß L das Pumping-Lemma erfüllen, es gilt also:

Es gibt eine Zahl n, so daß für alle x aus L mit |x| >= n eine Zerlegung x = uvw existiert, für die die drei Bedingungen des Pumping-Lemma erfüllt sind.

Insbesondere gilt dies also auch für das Wort
x = a^n b b a^n.

x hat offensichtlich die Länge 2n + 2 > n und muß daher die Bedingungen des Pumping-Lemmas erfüllen.

Nach diesen Bedingungen existiert eine Zerlegung x = uvw mit |v| >= 1 und |uv| <= n. Aufgrund der Struktur von x besteht uv also nur aus a's. Wir haben x somit wie folgt zerlegt:

x = u v w = a^|u| a^|v| a^(n - |u| - |v|) b b a^n

Nach dem Pumping-Lemma ist y = u v^0 w auch ein Wort der Sprache L. Es gilt:

y = u v^0 w = u w = a^|u| a^(n - |u| - |v|) b b a^n

Offensichtlich ist y aber kein Wort aus L, da gilt
y = a^(|u| + n - |u| - |v|) b b a^n = a^(n - |v|) b b a^n.

n - |v| ist nämlich ungleich n, die b's liegen somit nicht mehr in der Mitte des Wortes.

Daher muß die Annahme, daß L regulär ist, falsch sein.
The purpose of computing is insight, not numbers.
Richard Hamming, 1962

sebi

Junior Schreiberling

  • "sebi" is male

Posts: 153

Date of registration: Dec 10th 2001

Location: Hannover, Erde

Occupation: lebenskünstler

54

Tuesday, February 11th 2003, 3:20pm

ich danke dir aufs äusserste.

Quoted


x = a^n b b a^n.
x hat offensichtlich die Länge 2n + 2 > n


wo kommt da die +2 her ?
danke :)

  • "Joachim" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

55

Tuesday, February 11th 2003, 3:25pm

Quoted

Original von sebi

Quoted


x = a^n b b a^n.
x hat offensichtlich die Länge 2n + 2 > n


wo kommt da die +2 her ?
Ganz kleinschrittig:

|x|
= |a^n b b a^n|
= |a^n| + |b| + |b| + |a^n|
= n * |a| + 1 + 1 + n * |a|
= n * 1 + 1 + 1 + n * 1
= n + 1 + 1 + n
= 2*n + 2
The purpose of computing is insight, not numbers.
Richard Hamming, 1962

Cipher

Junior Schreiberling

  • "Cipher" is male

Posts: 156

Date of registration: Oct 15th 2002

Location: Berlin

Occupation: IT Application Consultant

56

Tuesday, February 11th 2003, 3:25pm

vielen dank @joachim !

Spike

Trainee

  • "Spike" is male

Posts: 41

Date of registration: Nov 8th 2002

Location: Würzburg

57

Tuesday, February 11th 2003, 3:25pm

Quoted

Original von Cipher
müssen wir in der klausur kellerautomaten mit endzuständen benutzen, oder reicht es als endzustand aus, wenn der keller leer ist?

im buch, dass ja als skript zur vorlesung verwendet wird, ist die definition eines kellers ja zunächst ohne endzustand (also, wird das wort durch leeren keller akzeptiert).

wurde in der vorlesung irgendwas festgelegt, oder ist das jedem selbst überlassen?

weil...(sorry, wenn ich mit der aufgabe nerve)...ohne Endzustand könnte doch Üb6 Aufg1 auch so aussehen, oder?

z0,a,# -> z0,A
z0,a,A -> z0,AA
z0,b,A -> z1,epsilon
z1,b,A -> z1,epsilon

Cipher



In der Klausur darf nur verwendet werden, was schon aus der Vorlesung bekannt ist. Da Kellerautomaten ohne Endzustände nicht in der Vorlesung eingeführt wurden, dürfen sie auch nicht in der Klausur verwendet werden.

sebi

Junior Schreiberling

  • "sebi" is male

Posts: 153

Date of registration: Dec 10th 2001

Location: Hannover, Erde

Occupation: lebenskünstler

sebi

Junior Schreiberling

  • "sebi" is male

Posts: 153

Date of registration: Dec 10th 2001

Location: Hannover, Erde

Occupation: lebenskünstler

59

Tuesday, February 11th 2003, 3:50pm

ich hoffe ich nerve nich :) (und wenn doch stehe ich dazu... :D )

x=a^n b b a^n
x= u v w

wenn ich dann |uv| <= n prüfe, habe ich
|a^n bb| = n +2 ungleich n

bin ich damit nicht schon fertig ?


Spike

Trainee

  • "Spike" is male

Posts: 41

Date of registration: Nov 8th 2002

Location: Würzburg

60

Tuesday, February 11th 2003, 4:29pm

Quoted

Original von sebi
ich hoffe ich nerve nich :) (und wenn doch stehe ich dazu... :D )

x=a^n b b a^n
x= u v w

wenn ich dann |uv| <= n prüfe, habe ich
|a^n bb| = n +2 ungleich n

bin ich damit nicht schon fertig ?



Ich verstehe dein Argument nicht. Wie hängt a^n b b mit uv zusammen?

Du willst doch zeigen, dass L nicht regulär ist.

Um mit Hilfe des Pumping-Lemmas zu zeigen, dass L nicht regulär ist, musst du folgendes beweisen:

Man kann ein x in L mit |x| >= n finden, so dass für jede beliebige Zerlegung von x in Teilworte uvw mit |uv| =< n und |v| > 0 gilt: Es gibt ein i >= 0, so dass u v^i w nicht in L ist.

Für die gegebene Sprache ist x = a^n b b a^n genau so ein Wort. Denn x ist in L, |x| = 2n +2 >= n. Für jede beliebige Zerlegung von x in Teilworte uvw mit |uv| =< n und |v| > 0 gilt u=a^k und v=a^l mit k+l =< n, also

x = a^k a^l a^(n-k-l) b b a^n

und damit gilt

u v^2 w = uvvw = a^k a^l a^l a^(n-k-l) b b a^n = a^(n+l) b b a^n.

Also kann man kein Wort y finden mit u v^2 w = y y^R. Also ist u v^2 w nicht in L.