Fachrat Informatik - Forum

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?)

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

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

Quoted from "Xular"

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.

Quoted from "Xular"

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.

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

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

Quoted from "cartman"

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 .

Quoted from "cartman"

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

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

Quoted from "Finn"

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.

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?

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

Quoted from "Skuld"

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?

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

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

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

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?

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.

Quoted from "Skuld"

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