Fachrat Informatik - Forum

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.

Go to the top of the page

Junior Schreiberling

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

Go to the top of the page

sr409

Junior Schreiberling

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.

Go to the top of the page

Guru

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

Go to the top of the page

Junior Schreiberling

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

Go to the top of the page

sr409

Junior Schreiberling

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 ?

Go to the top of the page

Guru

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

Go to the top of the page

Junior Schreiberling

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

venturemedia.de - you don't need eyes to see, you need a vision

Go to the top of the page

Junior Schreiberling

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...

Go to the top of the page

Guru

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

Go to the top of the page

Junior Schreiberling

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...

venturemedia.de - you don't need eyes to see, you need a vision

Go to the top of the page

Guru

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

Go to the top of the page

Junior Schreiberling

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

venturemedia.de - you don't need eyes to see, you need a vision

Go to the top of the page

Guru

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

Go to the top of the page

Junior Schreiberling

Date of registration: Oct 15th 2002

Location: Berlin

Occupation: IT Application Consultant

56

Tuesday, February 11th 2003, 3:25pm

vielen dank @joachim !

Go to the top of the page

Spike

Trainee

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.

Matthias Galota

Go to the top of the page

Junior Schreiberling

Date of registration: Dec 10th 2001

Location: Hannover, Erde

Occupation: lebenskünstler

58

Tuesday, February 11th 2003, 3:28pm

danke joachim

venturemedia.de - you don't need eyes to see, you need a vision

Go to the top of the page

Junior Schreiberling