You are not logged in.

Finn

Alter Hase

Posts: 126

Date of registration: Oct 10th 2010

61

Monday, February 28th 2011, 2:43pm



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
Regierungen der industriellen Welt,...

Skuld

Erfahrener Schreiberling

  • "Skuld" is male

Posts: 344

Date of registration: Oct 2nd 2007

Occupation: Student

62

Monday, February 28th 2011, 2:45pm


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

63

Monday, February 28th 2011, 2:54pm


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.

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.

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


mar1k

Trainee

Posts: 41

Date of registration: Oct 17th 2009

64

Monday, February 28th 2011, 2:55pm

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?

Nagezahn

Junior Schreiberling

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

Posts: 198

Date of registration: Feb 9th 2010

Location: Nordstadt

65

Monday, February 28th 2011, 2:57pm

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

b) Von welchem Typ ist die Sprache?
Typ 3, die Grammatik ist z.B.:
S->aA|aB1
A->aS
B1->bB2|b
B2->bB1

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


Skuld

Erfahrener Schreiberling

  • "Skuld" is male

Posts: 344

Date of registration: Oct 2nd 2007

Occupation: Student

66

Monday, February 28th 2011, 3:09pm

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

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.ä.?
Hello, IT, have you tried turning it off and on again?

Wo schlafen Schmetterlinge eigentlich?

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


Arne

ThI

  • "Arne" is male

Posts: 1,798

Date of registration: Oct 7th 2002

Location: Hannover :)

Occupation: Lecturer ThI

67

Monday, February 28th 2011, 3:56pm

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.
"NP - The class of dashed hopes and idle dreams." Complexity Zoo

Nagezahn

Junior Schreiberling

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

Posts: 198

Date of registration: Feb 9th 2010

Location: Nordstadt

68

Monday, February 28th 2011, 3:57pm

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

Arne

ThI

  • "Arne" is male

Posts: 1,798

Date of registration: Oct 7th 2002

Location: Hannover :)

Occupation: Lecturer ThI

69

Monday, February 28th 2011, 4:00pm

Ü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. :)
"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

70

Monday, February 28th 2011, 4:02pm

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?
Hello, IT, have you tried turning it off and on again?

Wo schlafen Schmetterlinge eigentlich?

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


Xular

Trainee

  • "Xular" is male

Posts: 62

Date of registration: Oct 7th 2007

71

Monday, February 28th 2011, 4:15pm

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

Skuld

Erfahrener Schreiberling

  • "Skuld" is male

Posts: 344

Date of registration: Oct 2nd 2007

Occupation: Student

72

Monday, February 28th 2011, 4:24pm

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.. :D Auch gut ^^
Hello, IT, have you tried turning it off and on again?

Wo schlafen Schmetterlinge eigentlich?

Xular

Trainee

  • "Xular" is male

Posts: 62

Date of registration: Oct 7th 2007

73

Monday, February 28th 2011, 4:26pm

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

newgame

Trainee

Posts: 45

Date of registration: Sep 30th 2009

74

Monday, February 28th 2011, 6:03pm

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

Finn

Alter Hase

Posts: 126

Date of registration: Oct 10th 2010

75

Monday, February 28th 2011, 6:08pm

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? 8| welcher neue Termin denn?? hab davon gar nichts mitbekommen..

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

mfg FInn
Regierungen der industriellen Welt,...

Skuld

Erfahrener Schreiberling

  • "Skuld" is male

Posts: 344

Date of registration: Oct 2nd 2007

Occupation: Student

76

Monday, February 28th 2011, 6:11pm

Vermutlich ist das Tauschen mit KvA gemeint. Ursprünglich sollte KvA morgen stattfinden und GTI letzten Dienstag. Wird schätzungsweise wieder Audimax sein.
Hello, IT, have you tried turning it off and on again?

Wo schlafen Schmetterlinge eigentlich?

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


Nagezahn

Junior Schreiberling

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

Posts: 198

Date of registration: Feb 9th 2010

Location: Nordstadt

77

Monday, February 28th 2011, 10:32pm

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?

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


Skuld

Erfahrener Schreiberling

  • "Skuld" is male

Posts: 344

Date of registration: Oct 2nd 2007

Occupation: Student

78

Tuesday, March 1st 2011, 12:05am

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.
Hello, IT, have you tried turning it off and on again?

Wo schlafen Schmetterlinge eigentlich?

gode

Zuhörer

  • "gode" is male

Posts: 2

Date of registration: Jul 28th 2007

79

Tuesday, March 1st 2011, 12:35am

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

thx

This post has been edited 1 times, last edit by "gode" (Mar 1st 2011, 12:39am)


Nagezahn

Junior Schreiberling

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

Posts: 198

Date of registration: Feb 9th 2010

Location: Nordstadt

80

Tuesday, March 1st 2011, 12:57am

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

thx
Damit ist gemeint, das mindestens so viele Nullen in jedem linken Teilwort enthalten sind wie 1en. Sprich das Wort 010010 hat die linken Teilwörter epsiolon, 0, 01, 010, 0100, 01001, 010010, und für alle diese Wörter muß die genannte Bedingung gelten.
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.
Nach meinem Verständnis hat die Zahl der Definitionslücken nichts mit Berechenbarkeit zu tun. Die Funktion, die von Mw berechnet wird, ist ja genau dort definiert, wo Mw nach endlich vielen Schritten hält - in ihrem Definitionsbereich ist sie also, wenn ich das richtig sehe, immer berechenbar. Unabhängig von der tatsächlichen Gestalt von Mw (bzw. w). Daraus, daß eine Funktion einen unendlich großen Definitionsbereich hat (undendlich viele x, für die Mw hält), läßt sich aber noch nicht schließen, daß sie nur endlich viele Definitionslücken hat. Sie könnte zum Beispiel für Eingaben mit gerader Länge definiert sein (also halten), für solche mit ungerader Länge undefiniert sein (in eine Endlosschleife geraten).

Davon abgesehen müßte in einem Fall, wo S die Menge der Funktionen mit endlich vielen Definitionslücken ist, aber ebenfalls die Voraussetzungen für die Anwendung des Satzes von Rice erfüllen.

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