Fachrat Informatik - Forum

Quoted from "Skuld"

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?

a) ja typ 2 denke ich auch
b)hier denke ich dass es typ 3 ist, habe hierfür ein automaten gebastelt, kann den auf wunsch auch nochmal digitalisieren

die sprache sind ja alle wörter mit a^i b^j |mit i,j ungerade

mfg Finn

Quoted from "Finn"

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

Hm dann wohl wirklich mit dem Wort 0^n 1^n 0^n 1^n, damit und zu uv²w aufgepumpt wird die Wortlänge insgesamt zu 5n, was ja nicht in jedem Fall gerade ist, also nicht in L.

Quoted from "Arne"

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 .

Ich dachte eigtl dass n mod m = n für m > n (z.B. 3 mod 5 = 3), sodass das Wort für |v|=n (wenn man von der obigen Zerlegung a^n-|v| b^n ausgeht) wieder zur Sprache gehört, da 0 mod n = 0, oder verstehe ich da was falsch?

Quoted from "Nagezahn"

Nein, das kannst du nicht annehmen. Es gilt ja nur |uv| <= n und |v| >= 1. Niemand verbietet dir, z.B. v = 00 zu wählen. Aufgepumpt gibt's dann 4n+2, das ist immer noch gerade. Allerdings verliert das Teilwort x 1en (die wandern zum Teilwort y rüber), ohne daß y dafür 0en bekommt.

Okay, verstehe. Wäre ich leider in einer Klausursituation nicht drauf gekommen (die Sache mit dem Trennstrich verschieben).

Wegen der Sprache: Ebenfalls verstanden, muss man halt zusehen, dass man so einen Automaten bzw. eine entsprechende Grammatik dann hinbekommt. Die Fragestellung deutet ja an, dass die Antworten zu a) und b) nicht identisch sind..

Und eine weitere Frage, dieses mal zum Satz von Rice. Arne hat das ja schon ausführlich erklärt, danke dafür. Aus der gleichen Klausur (WS09), Aufgabe 6:

Beweisen oder widerlegen Sie: Die Sprache INF := { w {0, 1}* | es gibt unendliche viele verschiedene Wörter x {0, 1}*, sodass bei Eingabe x hält }

Übertragen auf Funktionen sind dies also Funktionen mit unendlichem Definitionsbereich (überall wo die Funktion definiert ist, hält die Turingmaschine), also anders herum alle Funktionen, die nirgendwo undefiniert sind. Dies entspricht ja der Menge aller berechenbaren Funktionen , richtig? Und da man mit dem Satz von Rice nicht über diese Menge gehen darf, kann man den Satz nicht anwenden.
Reicht das nun als Begründung, dass die Sprache demzufolge entscheidbar ist, oder muss man die Entscheidbarkeit nun nachweisen, durch zB. rekursive Aufzählbarkeit o.ä.?

Quoted from "Arne"

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 .

Ich sehe, dass mir da gerade ein kleiner Fehler unterlaufen ist. Natürlich gilt für . In diesem Fall haut deine leider nicht ganz hin: wenn man die Zerlegung wähl, sodass v aus allen a's besteht, dann gilt für alle i immer, dass das gepumpte Wort in der Sprache ist. Dieses Problem kann man jedoch schnell beheben: setze das Startwort x einfach auf , dann gilt und . Damit gilt jedoch für i=0 und außerdem entscheidenderweise . Also insbesondere gilt niemals, dass 0 herauskommt.

Quoted from "Nagezahn"

Quoted from "Skuld"

Übertragen auf Funktionen sind dies also Funktionen mit unendlichem Definitionsbereich (überall wo die Funktion definiert ist, hält die Turingmaschine), also anders herum alle Funktionen, die nirgendwo undefiniert sind.

Warum das? Es heißt ja nicht, die Maschine hält bei jedem Eingabewort, sondern nur, daß es unendlich viele gibt.

Korrekt Nagezahn. Insbesondere könnte man auch sagen, dass man in diesem Fall alle die berechenbaren Funktionen wählt, die nur endlich viele Definitionslücken haben.

Abgesehen davon wäre die Menge aller vollständig definierten Funktionen auch nicht die Menge aller Funktionen, da ja insbesondere solche, die Definitionslücken (egal wie viele) haben, nicht dazu gehören.

Quoted from "cartman"

andere Aufgabe, L={a^n+m b^n c^m, n,m>=0}

Frage: ist L regulär ?

Also ich hab das folgendermaßen gelöst:

Wähle Wort ,

Nun müsste man ja eigentlich eine Fallunterscheidung durchführen:

1. n > 0

Gilt dies, besteht v nur aus a's, wegen . Pumpt man nun auf uv²w auf, erhält man ein Wort der Form , welches nicht in der Sprache liegt.

2. n = 0
a)

v besteht wiederum nur aus a's, das Wort hat die Form . Pumpt man wieder auf uv²w auf, hat man mehr a's als c's, also ist das Wort nicht in der Sprache.

b) m < n

Hier besteht v aus a's und c's, das Wort hat wieder die Form , mit x+y = m. Aus erneutem aufpumpen auf uv²w folgt, dass die c's im Verhältnis zu den a's weniger aufgepumpt werden, also gibt es im Endeffekt wieder mehr a's als c's und das Wort ist wieder nicht in der Sprache.

Stimmt das so?


----

Zu dem Satz von Rice:

D.h. wir haben die Menge der Funktionen mit endlich vielen Definitionslücken. Die müsste folglich berechenbar sein, es sind aber, wie ihr gesagt hab, nciht alle berechenbaren Funktionen, also kann man den Satz von Rice anwenden und es folgt Inf ist nicht entscheidbar?

Viel zu kompliziert gedacht, Skuld...

Du musst das PL nur für -irgendein- Wort, das in der Sprache liegt durchführen, also z.b. bei n = n und m = 0, dann hast du wieder das übliche a^n b^n

Quoted from "Xular"

Viel zu kompliziert gedacht, Skuld...

Du musst das PL nur für -irgendein- Wort, das in der Sprache liegt durchführen, also z.b. bei n = n und m = 0, dann hast du wieder das übliche a^n b^n

Oha, und dabei dacht ich dass meine 3-Fälle-Lösung schon zu simpel wäre.. Auch gut

Fallunterscheidungen musst du nur beim PL für kontextfreie Sprachen machen - das sollte man sich auch anschauen, kam ja in der letzten Klausur dran...

Mal nebenbei: Mir ist gerade aufgefallen, dass der Raum der Klausur in der E-Mail, in der uns der neue Klausurtermin mitgeteilt worden ist, nicht aufgefuehrt ist. Kann mir einer sagen welcher Raum es ist (Audimax?)?

Quoted from "newgame"

Mal nebenbei: Mir ist gerade aufgefallen, dass der Raum der Klausur in der E-Mail, in der uns der neue Klausurtermin mitgeteilt worden ist, nicht aufgefuehrt ist. Kann mir einer sagen welcher Raum es ist (Audimax?)?

Neuer Termin? welcher neue Termin denn?? hab davon gar nichts mitbekommen..

Aber Audimax ist doch E4** (ganz oben halt)

mfg FInn

Vermutlich ist das Tauschen mit KvA gemeint. Ursprünglich sollte KvA morgen stattfinden und GTI letzten Dienstag. Wird schätzungsweise wieder Audimax sein.

Quoted from "Nagezahn"

Quoted from "Skuld"

Beweisen oder widerlegen Sie: Die Sprache INF := { w {0, 1}* | es gibt unendliche viele verschiedene Wörter x {0, 1}*, sodass bei Eingabe x hält } ist entscheidbar.

Ich versuche mich auch gerade an dieser Aufgabe und sehe das zur Zeit so: S ist die Menge der berechenbaren Funktionen mit unendlichem Definitionsbereich. S ist ungleich R, da zum Beispiel Omega (überall undefiniert) nicht in S, aber berechenbar ist. Daß S nicht leer ist, sollte offensichtlich sein. Gemäß dem Satz von Rice ist INF also nicht entscheidbar.

Sehe ich das richtig? Wenn ja, gibt es formal etwas an der Begründung auszusetzen? Fehlt noch etwas (wenn ja, was?), um bei der Aufgabe volle Punktzahl zu erhalten?

BTW: weiß eigentlich jemand, ob bei dieser Klausur wieder nur ausgeteiltes Papier zugelassen ist?

Klingt für mich schlüssig. Was ist denn mit meiner Begründung (s.o.), kann man aus "hat endlich viele Definitionslücken" die Berechenbarkeit schließen? Somit wäre das dann unser S und dann funktioniert der Satz.

Ich schätze mal, dass wieder nur ausgeteiltes Papier zulässig ist, war bei KvA so und auch bei der GTI Klausur im Herbst.

Moin,
hat jemand die Lösung zu Aufgabe 5 aus der Klausur 09ws? Das mit dem Präfix verwirrt mich ein wenig.

thx