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.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?)
This post has been edited 1 times, last edit by "Nagezahn" (Feb 27th 2011, 3:15pm)
This post has been edited 1 times, last edit by "cartman" (Feb 27th 2011, 4:46pm)
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...
This post has been edited 1 times, last edit by "Arne" (Feb 27th 2011, 5:48pm)
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?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 ?
This post has been edited 1 times, last edit by "Nagezahn" (Feb 27th 2011, 6:54pm)
This post has been edited 1 times, last edit by "cartman" (Feb 28th 2011, 1:05pm)
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
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
Jede kontextfreie Sprache kann von einem deterministischen
Kellerautomaten akzeptiert werden.
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.
This post has been edited 2 times, last edit by "Skuld" (Feb 28th 2011, 1:49pm)
This post has been edited 1 times, last edit by "Xular" (Feb 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?
Quoted
Wähle also einfach das Wort x^n y^n , dann ist |x| = |y|
This post has been edited 1 times, last edit by "cartman" (Feb 28th 2011, 2:26pm)
This post has been edited 1 times, last edit by "Xular" (Feb 28th 2011, 2:29pm)
This post has been edited 2 times, last edit by "Skuld" (Feb 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?