Du bist nicht angemeldet.

Spike

Trainee

  • »Spike« ist männlich

Beiträge: 41

Registrierungsdatum: 08.11.2002

Wohnort: Würzburg

41

11.02.2003, 09:51

Zitat

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

Beiträge: 156

Registrierungsdatum: 03.01.2003

42

11.02.2003, 10:48

Zitat

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« ist männlich

Beiträge: 156

Registrierungsdatum: 15.10.2002

Wohnort: Berlin

Beruf: IT Application Consultant

43

11.02.2003, 13:05

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

Beiträge: 156

Registrierungsdatum: 03.01.2003

44

11.02.2003, 13:10

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« ist männlich

Beiträge: 2 863

Registrierungsdatum: 11.12.2001

Wohnort: Hämelerwald

Beruf: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

45

11.02.2003, 13:30

Zitat

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« ist männlich

Beiträge: 156

Registrierungsdatum: 15.10.2002

Wohnort: Berlin

Beruf: IT Application Consultant

46

11.02.2003, 14:10

Zitat

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

Beiträge: 156

Registrierungsdatum: 03.01.2003

47

11.02.2003, 14:21

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

x=abcd
x hoch R=dcba

korrekt ?

  • »Joachim« ist männlich

Beiträge: 2 863

Registrierungsdatum: 11.12.2001

Wohnort: Hämelerwald

Beruf: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

48

11.02.2003, 14:22

Zitat

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.


Zitat

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« ist männlich

Beiträge: 153

Registrierungsdatum: 10.12.2001

Wohnort: Hannover, Erde

Beruf: lebenskünstler

49

11.02.2003, 14:47

Zitat

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« ist männlich

Beiträge: 156

Registrierungsdatum: 15.10.2002

Wohnort: Berlin

Beruf: IT Application Consultant

50

11.02.2003, 14:50

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« ist männlich

Beiträge: 2 863

Registrierungsdatum: 11.12.2001

Wohnort: Hämelerwald

Beruf: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

51

11.02.2003, 14:58

Zitat

Original von sebi

Zitat

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.

Zitat

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« ist männlich

Beiträge: 153

Registrierungsdatum: 10.12.2001

Wohnort: Hannover, Erde

Beruf: lebenskünstler

52

11.02.2003, 15:03

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« ist männlich

Beiträge: 2 863

Registrierungsdatum: 11.12.2001

Wohnort: Hämelerwald

Beruf: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

53

11.02.2003, 15:14

Zitat

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« ist männlich

Beiträge: 153

Registrierungsdatum: 10.12.2001

Wohnort: Hannover, Erde

Beruf: lebenskünstler

54

11.02.2003, 15:20

ich danke dir aufs äusserste.

Zitat


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


wo kommt da die +2 her ?
danke :)

  • »Joachim« ist männlich

Beiträge: 2 863

Registrierungsdatum: 11.12.2001

Wohnort: Hämelerwald

Beruf: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

55

11.02.2003, 15:25

Zitat

Original von sebi

Zitat


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« ist männlich

Beiträge: 156

Registrierungsdatum: 15.10.2002

Wohnort: Berlin

Beruf: IT Application Consultant

56

11.02.2003, 15:25

vielen dank @joachim !

Spike

Trainee

  • »Spike« ist männlich

Beiträge: 41

Registrierungsdatum: 08.11.2002

Wohnort: Würzburg

57

11.02.2003, 15:25

Zitat

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« ist männlich

Beiträge: 153

Registrierungsdatum: 10.12.2001

Wohnort: Hannover, Erde

Beruf: lebenskünstler

sebi

Junior Schreiberling

  • »sebi« ist männlich

Beiträge: 153

Registrierungsdatum: 10.12.2001

Wohnort: Hannover, Erde

Beruf: lebenskünstler

59

11.02.2003, 15:50

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« ist männlich

Beiträge: 41

Registrierungsdatum: 08.11.2002

Wohnort: Würzburg

60

11.02.2003, 16:29

Zitat

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.