You are not logged in.

Skuld

Erfahrener Schreiberling

  • "Skuld" is male

Posts: 344

Date of registration: Oct 2nd 2007

Occupation: Student

41

Sunday, February 27th 2011, 2:41pm

Naja die Definition ist, dass es nur endlich viele Wörter x gibt, bei der die Maschine hält. Lässt sich also durch eine Funktion mit endlichem Wertebreich darstellen. Und diese sind, so weit ich das verstanden habe, nach dem Satz von Rice nicht entscheidbar.

Ich hab das so verstanden, dass der Satz von Rice im Prinzip sagt: "Jede Sprache, deren Turingmaschine durch eine berechenbare Funktion dargestellt werden kann, ist nicht entscheidbar."
Was aber a) paradox klingt und b) vermutlich nicht stimmt. Ich wäre auch für eine ausführlichere Erklärung dankbar.


Ich hab selber auch noch eine Frage, zB. zur Klausur vom Februar 2010, Aufgabe 2:
"Geben Sie einen DEA M an, für den gilt: L(M) = { w {0, 1}* | w ist die Binärdarstellung (evtl. mit führenden Nullen) einer Zahl , die durch 3 teilbar ist}

Wie geht man an sowas ran? Ich habe mir die ersten zehn durch 3 teilbaren Zahlen in Binärdarstellung aufgeschrieben, in der Hoffnung da ein Muster zu erkennen, was aber leider nicht der Fall ist (vielleicht seh ichs einfach nur nicht?)
Hello, IT, have you tried turning it off and on again?

Wo schlafen Schmetterlinge eigentlich?

Nagezahn

Junior Schreiberling

  • "Nagezahn" is male
  • "Nagezahn" started this thread

Posts: 198

Date of registration: Feb 9th 2010

Location: Nordstadt

42

Sunday, February 27th 2011, 2:50pm

Ich hab selber auch noch eine Frage, zB. zur Klausur vom Februar 2010, Aufgabe 2:
"Geben Sie einen DEA M an, für den gilt: L(M) = { w {0, 1}* | w ist die Binärdarstellung (evtl. mit führenden Nullen) einer Zahl , die durch 3 teilbar ist}

Wie geht man an sowas ran? Ich habe mir die ersten zehn durch 3 teilbaren Zahlen in Binärdarstellung aufgeschrieben, in der Hoffnung da ein Muster zu erkennen, was aber leider nicht der Fall ist (vielleicht seh ichs einfach nur nicht?)
Ich habe es mir so gedacht: Wenn man das Wort von links nach rechts durchgeht, dann fügt jedes gesetzte Bit der Zahl einen Wert hinzu, der % 3 abwechselnd 1 bzw. 2 ergibt*. In den Zuständen speichert man dann, wie groß der Rest bei einer Division durch 3 gerade ist. Ganz durchdacht oder getestet habe ich es noch nicht, aber das mal als Ansatz.

* Siehe die folgende Tabelle:
1 % 3 = 1
2 % 3 = 2
4 % 3 = 1
8 % 3 = 2
16 % 3 = 1
...

[Edit]
Hier mal mein Entwurf, getestet von 0 bis 15 mit grader und ungrader Anzahl an Bits:

This post has been edited 1 times, last edit by "Nagezahn" (Feb 27th 2011, 3:15pm)


cartman

Junior Schreiberling

  • "cartman" is male

Posts: 154

Date of registration: Mar 10th 2009

Location: Laatzen

43

Sunday, February 27th 2011, 4:45pm

zu dem einen Automaten L:={w€{a,b}* | w=a* oder |w|_b mod 3 = 1}
gab es noch eine Zusatzfrage:

Ist die Sprache L auch vom Typ 2, wenn ja, geben sie eine kontextfreie Grammatik an, die L erzeugt. Falls nein, warum ist sie nicht kontextfrei ?

Kann man sowas irgendwie sehen (falls ja, wie/woran) um dann entscheiden zu können, ob man eine Grammatik "baut" oder ans Pumping Lemma geht ?

und wären das Produktionen einer kontextfreien Grammatik dazu ?
S->€|a|b|aX|bY
X->a|aX
Y->bbb|bbbY

This post has been edited 1 times, last edit by "cartman" (Feb 27th 2011, 4:46pm)


Xular

Trainee

  • "Xular" is male

Posts: 62

Date of registration: Oct 7th 2007

44

Sunday, February 27th 2011, 5:19pm

Ich habe noch eine Sache gefunden, die mich verwirrt:

Lemma aus dem Skript: A,B Sprachen; A reduzierbar auf B und B entscheidbar => A ist auch entscheidbar

Klausurkurzfrage der SS10 Klausur: Für jede unentscheidbare Sprache L gibt es eine entscheidbare Sprache L', so dass L Teilmenge von L' ist
Musterlösung sagt: richtig

Wenn eine Sprache eine Teilmenge einer anderen ist, so kann man diese Sprache doch auch auf die andere reduzieren oder nicht? Dann wäre das ein Widerspruch, weil die unentscheidbare Sprache dann offensichtlich doch entscheidbar sein müsste... Was hab ich daran falsch verstanden?


Wäre auch noch super wenn jemand eine ausführlichere Erklärung zum Satz von Rice liefern kann (siehe vorherige Seite, letzter Post), Skuld ist sich da ja auch nicht so ganz sicher... ;)

Arne

ThI

  • "Arne" is male

Posts: 1,798

Date of registration: Oct 7th 2002

Location: Hannover :)

Occupation: Lecturer ThI

45

Sunday, February 27th 2011, 5:48pm

Ich habe noch eine Sache gefunden, die mich verwirrt:

Lemma aus dem Skript: A,B Sprachen; A reduzierbar auf B und B entscheidbar => A ist auch entscheidbar

Klausurkurzfrage der SS10 Klausur: Für jede unentscheidbare Sprache L gibt es eine entscheidbare Sprache L', so dass L Teilmenge von L' ist
Musterlösung sagt: richtig

Wenn eine Sprache eine Teilmenge einer anderen ist, so kann man diese Sprache doch auch auf die andere reduzieren oder nicht? Dann wäre das ein Widerspruch, weil die unentscheidbare Sprache dann offensichtlich doch entscheidbar sein müsste... Was hab ich daran falsch verstanden?


Dass dies Aussage mit der Teilmengenreduzierbarkeit nicht stimmen kann, sollte leicht dadurch verständlich werden, dass *jede* Sprache eine Obermenge der leeren Menge ist und die leere Menge bekanntlich regulär, und damit insbesondere entscheidbar ist. Die leere Menge ist übrigens auch die Begründung, warum die Kurzfrage als Antwort richtig bekommt.


Wäre auch noch super wenn jemand eine ausführlichere Erklärung zum Satz von Rice liefern kann (siehe vorherige Seite, letzter Post), Skuld ist sich da ja auch nicht so ganz sicher... ;)


Hier noch mal eine Intuition zum Satz von Rice. Der Satz von Rice lautet ja bekanntlich wie folgt: Sei eine Menge von berechenbaren Funktionen, die weder leer ist noch *alle* berechenbaren Funktionen umfasst. Dann ist nicht entscheidbar. Warum das jetzt genau so ist, kann man detailliert im Skript beim Beweis nachlesen und lasse ich jetzt erstmal weg. Wer konkrete Verständnis-Fragen zu bestimmten Stellen im Beweis hat, kann die aber natürlich gerne stellen.
Kommen wir dazu wie man den Satz benutzt. Habe ich nun eine Sprache L für die ich zeigen soll, dass sie unentscheidbar ist, kann ich versuchen die oben angesprochene Menge S anzugeben, sodass die sozusagen die Sprache L überdeckt. Kann man zeigen das dieses gilt, so kann man sofort mit dem Satz von Rice die Unentscheidbarkeit von L folgern.



Hier fällt sofort auf, dass nur Wörter (also in unserem Fall natürlich Gödelisierungen von Turing Maschinen und damit konkret Turing Maschinen an sich) in der Sprache sind, für die es nur endlich viele Wörter gibt, bei denen die TM hält. Das ist ja genau die Definition der Sprache L. Wenn man diese Eigenschaft auf mathematische Funktionen überträgt, dann entsprechen ja Definitionslücken eben genau Fällen, wo die Maschine *nie* hält und in eine Endlosschleife geht. Damit sind Eingabewerte, für die M hält folglich definiert und gehören damit zum Definitionsbereich. Also betrachtet L im Endeffekt nur solche Funktionen, die für endliche viele Eingaben definiert sind, also einen endlichen Definitionsbereich haben. Setzen wir nun S als die Menge aller berechenbaren Funktionen, die einen endlichen Definitionsbereich haben, so gilt C(S)=L. Damit ist L unendscheidbar nach dem Satz von Rice.
"NP - The class of dashed hopes and idle dreams." Complexity Zoo

This post has been edited 1 times, last edit by "Arne" (Feb 27th 2011, 5:48pm)


Xular

Trainee

  • "Xular" is male

Posts: 62

Date of registration: Oct 7th 2007

46

Sunday, February 27th 2011, 6:24pm

Danke für die ausführliche Antwort, Arne - hat mir sehr weitergeholfen :)

Nagezahn

Junior Schreiberling

  • "Nagezahn" is male
  • "Nagezahn" started this thread

Posts: 198

Date of registration: Feb 9th 2010

Location: Nordstadt

47

Sunday, February 27th 2011, 6:43pm

Ist die Sprache L auch vom Typ 2, wenn ja, geben sie eine kontextfreie Grammatik an, die L erzeugt. Falls nein, warum ist sie nicht kontextfrei ?
Es gibt einen DEA, der genau die Wörter der Sprache akzeptiert, damit ist die Sprache vom Typ 3, also auch vom Typ 2. Oder übersehe ich hier was Grundlegendes?

Eine kontextfreie Grammatik müßte zum Beispiel diese sein:
S -> ε | A | B (entscheiden zwischen den beiden Möglichkeiten)
A -> a | aA (beliebig viele as erzeugen)
B -> b | bC | Cb (zunächst genau ein b erzeugen)
C -> A | BBB (as oder 3 weitere bs erzeugen)

This post has been edited 1 times, last edit by "Nagezahn" (Feb 27th 2011, 6:54pm)


cartman

Junior Schreiberling

  • "cartman" is male

Posts: 154

Date of registration: Mar 10th 2009

Location: Laatzen

48

Monday, February 28th 2011, 1:04pm

nochmal dazu
L:={a^n b^m | n mod m = 0}

Zu zeigen : L ist nicht regulär

ich zögere da wie gesagt, bei der Wahl des Wortes x,

man könnte n=m annehmen, dann ist die Bedingung erfüllt, wenn n>=1
also x=a^n b^n
- uv besteht nur aus a's
- v aus mindestens einem a

wenn ich dann u v^0 w annehme, dann gilt a^n-|v| b^n, es gibt also weniger a's als b's, aber mindestens eins, also L nicht regulär

This post has been edited 1 times, last edit by "cartman" (Feb 28th 2011, 1:05pm)


Arne

ThI

  • "Arne" is male

Posts: 1,798

Date of registration: Oct 7th 2002

Location: Hannover :)

Occupation: Lecturer ThI

49

Monday, February 28th 2011, 1:08pm

nochmal dazu
L:={a^n b^m | n mod m = 0}

Zu zeigen : L ist nicht regulär

ich zögere da wie gesagt, bei der Wahl des Wortes x,

man könnte n=m annehmen, dann ist die Bedingung erfüllt, wenn n>=1
also x=a^n b^n
- uv besteht nur aus a's
- v aus mindestens einem a

wenn ich dann u v^0 w annehme, dann gilt a^n-|v| b^n, es gibt also weniger a's als b's, aber mindestens eins, also L nicht regulär

Genau, da für .
"NP - The class of dashed hopes and idle dreams." Complexity Zoo

Finn

Alter Hase

Posts: 126

Date of registration: Oct 10th 2010

50

Monday, February 28th 2011, 1:10pm

nochmal dazu
L:={a^n b^m | n mod m = 0}

Zu zeigen : L ist nicht regulär

ich zögere da wie gesagt, bei der Wahl des Wortes x,

man könnte n=m annehmen, dann ist die Bedingung erfüllt, wenn n>=1
also x=a^n b^n
- uv besteht nur aus a's
- v aus mindestens einem a

wenn ich dann u v^0 w annehme, dann gilt a^n-|v| b^n, es gibt also weniger a's als b's, aber mindestens eins, also L nicht regulär

jo, denke das ist richtig, man muss aber glaube noch kurz erwähnen, dass das wort x länger(gleich) ist als n, also |x| >= n
Regierungen der industriellen Welt,...

Finn

Alter Hase

Posts: 126

Date of registration: Oct 10th 2010

51

Monday, February 28th 2011, 1:21pm

Ich hab auch mal eine Frage,

In der Klausur ws09 ist die Frage:

Quoted

Jede kontextfreie Sprache kann von einem deterministischen
Kellerautomaten akzeptiert werden.

Wikipedia hat auch die Antwort:

Quoted

Ein deterministischer Kellerautomat (DPDA) erkennt die deterministisch-kontextfreien Sprachen, also nur eine echte Teilmenge der kontextfreien Sprachen.

Aber ich dachte, das wäre noch eins der ungelösten Probleme, die Äquivalenz zwischen Det. Keller. und nicht Det. Keller.

mfg Finn
Regierungen der industriellen Welt,...

Arne

ThI

  • "Arne" is male

Posts: 1,798

Date of registration: Oct 7th 2002

Location: Hannover :)

Occupation: Lecturer ThI

52

Monday, February 28th 2011, 1:26pm

Aber ich dachte, das wäre noch eins der ungelösten Probleme, die Äquivalenz zwischen Det. Keller. und nicht Det. Keller.

Das musst Du mit den LBAen verwechselt haben. Es ist offen, ob det. LBA nicht schon ausreichen, um alle kontextsensitiven Sprachen zu akzeptieren. Folglich die Frage, ob NSPACE(n)=SPACE(n) gilt.
"NP - The class of dashed hopes and idle dreams." Complexity Zoo

Skuld

Erfahrener Schreiberling

  • "Skuld" is male

Posts: 344

Date of registration: Oct 2nd 2007

Occupation: Student

53

Monday, February 28th 2011, 1:44pm

Steht auch im Skript auf Seite 18 oben:

Satz: Eine Sprache L ist kontextfrei gdw. es einen NKA M gibt mit L = L(M).

Bemerkung: Es gibt auch deterministische Kellerautomaten (DKA). Obiger Satz gilt nicht für deterministische Kellerautomaten. Zum Beispiel kann die kontextfreie Sprache { {a, b} } von keinem DKA akzeptiert werden. DKAen akzeptieren also nur eine echte Teilmenge der kontextfreien Sprachen.



Hab auch noch ne Frage zu der Sprache, die bereits auf Seite 1 gepostet wurde:

L:= {xy | x,y € {0,1}*, |x|=|y| und |x|_1 + |y|_0 = |x| = |y|}

Zeigen bzw. widerlegen dass die Sprache regulär ist.
1.) Wie mach ich fest ob ich nun Pumping Lemma oder einen DEA anwende?
2.) Was für ein Wort könnte man wählen, wenn man Pumping Lemma anwendet? Ich kann mir da irgendwie nichts vorstellen. Oder ist das ein Hinweis darauf, dass ich es lieber mit einem DEA versuchen sollte? :D
Hello, IT, have you tried turning it off and on again?

Wo schlafen Schmetterlinge eigentlich?

This post has been edited 2 times, last edit by "Skuld" (Feb 28th 2011, 1:49pm)


Xular

Trainee

  • "Xular" is male

Posts: 62

Date of registration: Oct 7th 2007

54

Monday, February 28th 2011, 2:17pm

Du hast da ja einen logischen ausdruck hinter dem komma, also x1 UND x2 muss gelten. Folglich reicht es zu zeigen, dass x1 nicht gilt mit dem PL.

Wähle also einfach das Wort x^n y^n , dann ist |x| = |y| - dann wende das PL darauf an und tataa...

Wäre jedenfalls mein Ansatz.


edit: Wenn du ein Wort für beide Teile haben möchtest könntest du z.b. 0^n 1^n 0^n 1^n wählen, damit ist |x|=|y| und |x|_1 + |y|_0 = |x| = |y| ist auch erfüllt. Dann pumpst du die erste 0 auf und siehst, dass weder x1 noch x2 noch erfüllt werden...

This post has been edited 1 times, last edit by "Xular" (Feb 28th 2011, 2:24pm)


Finn

Alter Hase

Posts: 126

Date of registration: Oct 10th 2010

55

Monday, February 28th 2011, 2:24pm


L:= {xy | x,y € {0,1}*, |x|=|y| und |x|_1 + |y|_0 = |x| = |y|}

Zeigen bzw. widerlegen dass die Sprache regulär ist.
1.) Wie mach ich fest ob ich nun Pumping Lemma oder einen DEA anwende?
2.) Was für ein Wort könnte man wählen, wenn man Pumping Lemma anwendet? Ich kann mir da irgendwie nichts vorstellen. Oder ist das ein Hinweis darauf, dass ich es lieber mit einem DEA versuchen sollte? :D


wenn man das umstellt,

|x|_1 + |y|_0 = |x| = |y|

dann bekommt man da |x|_1 = |y|_1 und das gleich mit 0 raus

ich habs dann mit dem wort 1^n 0^n 1^n 0^n gemacht

mfg Finn
Regierungen der industriellen Welt,...

cartman

Junior Schreiberling

  • "cartman" is male

Posts: 154

Date of registration: Mar 10th 2009

Location: Laatzen

56

Monday, February 28th 2011, 2:25pm

Quoted

Wähle also einfach das Wort x^n y^n , dann ist |x| = |y|


ja, aber in dem Punkt, muss ja auch noch der zweite logische Ausdruck gelten,
sollte man in dem Fall nicht eher x=1^n 1^n wählen , in dem Fall wären ja beide Bedingungen erfüllt, und jetzt mit dem P.L. weitermachen, und dann werden es z.B. durchs aufpumpen mehr 1en in der ersten Worthälfte und dann ist es nicht mehr erfüllt

mein Problem hier wäre/ist eher, dass ich die Bedingungen überhaupt nicht kapiert habe und in der Klausur wahrscheinlich auch nicht kapieren würde, so ohne Erklärung

This post has been edited 1 times, last edit by "cartman" (Feb 28th 2011, 2:26pm)


Xular

Trainee

  • "Xular" is male

Posts: 62

Date of registration: Oct 7th 2007

57

Monday, February 28th 2011, 2:29pm

L:= {xy | x,y € {0,1}*, |x|=|y| und |x|_1 + |y|_0 = |x| = |y|}

Die Bedingungen sagen einfach, dass die Wortlänge von x = Wortlänge von y sein muss und der Betrag der 1en in x PLUS der Betrag der 0en in y gleich der Wortlänge von x = Wortlänge von y sein soll....

Ich frag mich allerdings gerade irgendwie, warum |x| = |y| so doppelt gemoppelt da drin is ;)

This post has been edited 1 times, last edit by "Xular" (Feb 28th 2011, 2:29pm)


Skuld

Erfahrener Schreiberling

  • "Skuld" is male

Posts: 344

Date of registration: Oct 2nd 2007

Occupation: Student

58

Monday, February 28th 2011, 2:37pm

Also nochmal zusammengefasst:

Wähle das Wort z = , |z| = 2n n

Nach den Bedingungen des PL kann nun z = uvw so aufgeteilt werden, dass und . Daraus folgt, dass v nur aus dem Präfix besteht (da dieses bereits die Länge n hat).
Pumpt man nun auf auf uv²w, ist das Präfix doppelt so lang wie das Suffix, somit ist uv²w nicht in L, also L nicht regulär?

Gut, dann ist mir das klar, war mir nur nicht sicher, ob man einfach das Wort darf.

Dann hab ich noch eine Frage zur Klausur 09 WS, Aufgabe 4:
Wir haben eine Grammatik mit den Produktionen: S -> AB, A -> aAa | a, B -> bBb | b

a) Von welchem Typ ist die Grammatik?
b) Von welchem Typ ist die Sprache?

Die Grammatik ist ja kontextfrei, also Typ 2, was leicht an der Definition der Typen zu sehen ist.
Ich würde behaupten, dass die Sprache auch vom Typ 2 ist, da ich keine Typ 3 Grammatik zustande bekommen habe, die die Sprache beschreibt. Wie muss ich das nun begründen? Einfach mutig behaupten "da keine Typ 3 Grammatik existiert, die die Sprache beschreibt"? Oder kann ich das irgendwie zeigen?
Hello, IT, have you tried turning it off and on again?

Wo schlafen Schmetterlinge eigentlich?

This post has been edited 2 times, last edit by "Skuld" (Feb 28th 2011, 2:41pm)


Xular

Trainee

  • "Xular" is male

Posts: 62

Date of registration: Oct 7th 2007

59

Monday, February 28th 2011, 2:40pm

Wäre mein erster Ansatz, allerdings hab ich vermutlich wieder "falschrum" gedacht und man muss doch beide Bedingungen erfüllen, da eine weniger eingeschränkte Sprache ja nicht regulär und eine stärker eingeschränkte Sprache regulär sein kann...

Also wähle lieber 0^n 1^n 0^n 1^n als Wort, der Rest bleibt ja das gleiche.

Finn

Alter Hase

Posts: 126

Date of registration: Oct 10th 2010

60

Monday, February 28th 2011, 2:41pm

Also nochmal zusammengefasst:

Wähle das Wort z = , |z| = 2n n

Nach den Bedingungen des PL kann nun z = uvw so aufgeteilt werden, dass und . Daraus folgt, dass v nur aus dem Präfix besteht (da dieses bereits die Länge n hat).
Pumpt man nun auf auf uv²w, ist das Präfix doppelt so lang wie das Suffix, somit ist uv²w nicht in L, also L nicht regulär?


ich denke das geht so nicht, da die Trennlinie nicht fest ist...

zB das wort 1111 ist in der sprache

11|11 hier ist die trennung zwischen x und y

wenn ich jetzt x pumpe: 1111|11 zB dann verschiebt sich die mitte 111|111 und das wort ist noch immer drin

mfg Finn
Regierungen der industriellen Welt,...