Dies ist eine statische Kopie unseres alten Forums. Es sind keine Interaktionen möglich.
This is a static copy of our old forum. Interactions are not possible.

Peter

Praktikant

Posts: 31

Date of registration: Feb 1st 2008

21

Tuesday, August 31st 2010, 3:34pm

Nur für Typ 3, nicht für Typ 2.
Beweis für Typ 2: Wenn die Menge der Typ-2-Sprachen unter Komplement abgeschlossen wäre, dann wäre sie, da sie ja unter Vereinigung abgeschlossen ist, nach deMorgan auch unter Schnitt abgeschlossen und das kann nicht sein - wegen

PS an die Forums-Admins: Diese Latex-Funktion ist seeehr cool :)

This post has been edited 1 times, last edit by "Peter" (Sep 1st 2010, 9:26am)


Xular

Trainee

  • "Xular" is male

Posts: 62

Date of registration: Oct 7th 2007

22

Tuesday, August 31st 2010, 3:43pm

Okay, Danke!

Der Wiki Artikel dazu ist leider etwas verwirrend: http://de.wikipedia.org/wiki/Kontextfreie_Sprache

Unter Eigenschaften > Komplement

Naja, merk ich mir dann halt so, dass das nur für Typ 3 gilt :)

Peter

Praktikant

Posts: 31

Date of registration: Feb 1st 2008

23

Tuesday, August 31st 2010, 3:46pm

Aber in dem WIki-Artikel steht doch Komplement unter den Eigenschaften, bei denen steht "nicht abgeschlossen unter..."

FSW16

Trainee

  • "FSW16" is male

Posts: 119

Date of registration: Jun 25th 2008

Location: Hildesheim

24

Tuesday, August 31st 2010, 3:51pm

Und wie geht man bei Aufgabe 3 und 6 vor?
Bei Aufgabe 3 Pumping-Lemma?

Xular

Trainee

  • "Xular" is male

Posts: 62

Date of registration: Oct 7th 2007

25

Tuesday, August 31st 2010, 3:58pm

Ja, und direkt unter Komplement dann "Seien L1,L2 kontextfrei und kontextfreie Sprachen unter Komplementbildung abgeschlossen. Dann sind auch...." - egal ;)


Was die Aufgabe 3 angeht, würde es da schon reichen, zu zeigen, dass die Bedingung |x| = |y| nicht erfüllt werden kann?
Das läuft ja auf x^n y^n hinaus, wenn x,y aus einem Zeichen bestehen (z.b. x = 1, y = 0) -> Standardwiderlegung mit PL

Und wenn eine Bedingung der Sprache nicht erfüllt werden kann, dann ist die andere ja irrelevant.

This post has been edited 1 times, last edit by "Xular" (Aug 31st 2010, 4:00pm)


Peter

Praktikant

Posts: 31

Date of registration: Feb 1st 2008

26

Tuesday, August 31st 2010, 3:59pm

A3: Genau, Pumping Lemma:

Dann kommt man auf und somit .
Für die Zerlegung , für die gilt, ergibt sich somit:
und daher .

A6: Satz von Rice:
Inf = C(S) für S = Menge aller berechenbarer Funktionen mit unendlichem Definitionsbereich
, da die Konstant-1-Funktion in S liegt und S ungleich der Menge aller berechenbarer Funktionen, da die überall undefinierte Funktion nicht in S liegt.

FSW16

Trainee

  • "FSW16" is male

Posts: 119

Date of registration: Jun 25th 2008

Location: Hildesheim

27

Tuesday, August 31st 2010, 4:07pm

Ok, Aufgabe 3 habe ich soweit verstanden nur Aufgabe 6 noch nicht ganz, aber ich muss mir auch erst noch einmal den Satz von Rice genau angucken.

Aber erstmal vielen Dank.

Peter

Praktikant

Posts: 31

Date of registration: Feb 1st 2008

28

Tuesday, August 31st 2010, 4:07pm

@Xular:
Zu den Typ-2-Sprachen: Aber das steht da ja beim Beweis durch Widerspruch für die Nichtabgeschlossenheit. Ich gebe zu, dass da das Wörtchen "Beweis" fehlt, aber wenn man sorgfältig liest und auch bei den anderen Eigenschaften einen Blick drauf wirft, bei denen ist es ja genauso gemacht vom Stil her, dann ist klar, was gemeint ist.
" - egal ;)": Ja, da hast du eigentlich recht, aber es geht um den allgemeinen Punkt, dass man in der Theorie halt sehr präzise sein muss (und das gilt halt auch fürs Lesen ;) ). (Und es geht um allgemeine mathematische Rechthaberei :D.)
Zur Aufgabe 3: Nein, so geht das nicht. Denn die Bedingung |x| = |y| kann ja gar nicht einfach verletzt werden. Für welche x und y soll man sie denn kaputt machen? Es ist ja gerade umgekehrt so, dass die Zerlegung xy dadurch definiert wird, dass |x|=|y| gelten soll.

@FSW16:
Wenn du morgen mitschreibst, dann empfehle ich dir das dringend, den genau anzugucken ;)

Xular

Trainee

  • "Xular" is male

Posts: 62

Date of registration: Oct 7th 2007

29

Tuesday, August 31st 2010, 4:22pm

zu 3:
Ich würde sagen, es gibt keinen DEA, der entscheiden kann, ob bei einem Wort xy |x| = |y| ist,
weil ein DEA nunmal keinen Speicher hat: Er kann nicht speichern, wie lang das Wort x ist um zu prüfen, ob y genauso lang ist.

Und genau das kann man ja auch mit dem PL beweisen - wähle z.b. x = 1^n und y = 0^n (ohne Beachtung der zweiten Bedingung),
dann ist xy = 1^n 0^n = uvw -> v besteht nur aus Einsen, weil |uv| <= n und |v| >= 1
dann ist uv^0w = 1^n-|v| 0^n und schon ist die Bedingung |x| = |y| verletzt, weil |v| >= 1 ist und damit |x| < |y|

Das ist mein Gedankengang dazu - Wenn man natürlich annimmt, dass |x| = |y| gegeben ist und gilt und man mit der Bedingung die zweite "angreifen" soll, dann würde ich wohl auch auf Ihre Lösung kommen ;)

Peter

Praktikant

Posts: 31

Date of registration: Feb 1st 2008

30

Tuesday, August 31st 2010, 4:30pm

Aber so wie das Problem formuliert ist, ist eindeutig festgelegt, dass |x|=|y|, denn L ist die "Menge aller Wörter xy" für die die beiden angegebenen Eigenschaften gelten. Das kann man äquivalent formulieren als "Menge aller Wörter z, für die es eine Zerlegung z=xy gibt", so dass die Eigenschaften gelten.
Wenn man jetzt beim Beweis zeigen soll, dass ein Wort nicht in der Sprache ist, muss man also zeigen, dass es sich nicht in Teilwörter x und y zerlegen lässt, es also keine Zerlegung gibt mit den angegebenen Eigenschaften. Ist das ganze jetzt klarer?
Ansonsten kannst du mich auch gerne anrufen oder noch vorbeikommen: 051176219633, Appelstr. 4, Raum 226. Ich bin noch bis 16.50 Uhr hier und morgen ab ca. 9 Uhr.

Xular

Trainee

  • "Xular" is male

Posts: 62

Date of registration: Oct 7th 2007

31

Tuesday, August 31st 2010, 5:08pm

Es ist ja nicht so, als würde die oben genannte (richtige) Lösung keinen Sinn ergeben - ich habe mich nur gefragt ob man die Aufgabe auch einfacher lösen kann.

In der Aufgabe wird ja folgende Formulierung benutzt:

L1:= {wort | wort besteht aus... , logische bedingung 1 AND logische bedingung 2 }

Jetzt dachte mich mir, dass wenn die allgemeinere Sprache

L2:= {wort | wort besteht aus... , logische bedingung 1 }

schon nicht regulär ist, dann kann die präzisierte Sprache L1 natürlich auch nicht regulär sein.

Das PL selber hab ich mittlerweile verstanden - falls morgen dann zwei log. Bedingungen verlangt werden muss ich wohl beide benutzen und kann nicht vereinfachen, schade ;)

Werd mich jetzt mal dem Satz von Rice widmen nach dem hint oben ;)

Peter

Praktikant

Posts: 31

Date of registration: Feb 1st 2008

32

Tuesday, August 31st 2010, 5:47pm

Also 1. ist in diesem Fall die allgemeinere Sprache L2 schon regulär, da sie die Sprache aller Wörter gerader Länge ist.
Und 2. gilt das i.A. nicht, was du vermutet hast: Wenn z.B. die "logische Bedingung 2" die Sprache L1 so weit einschränkt, dass sie endlich wird, dann ist sie regulär, auch wenn L2 nicht regulär ist.

Xular

Trainee

  • "Xular" is male

Posts: 62

Date of registration: Oct 7th 2007

33

Tuesday, August 31st 2010, 5:49pm

Ok, Danke für die Antworten :)

Panoramix

Trainee

  • "Panoramix" started this thread

Posts: 115

Date of registration: Sep 12th 2008

34

Tuesday, August 31st 2010, 5:49pm

Ich würde sagen, es gibt keinen DEA, der entscheiden kann, ob bei einem Wort xy |x| = |y| ist,
weil ein DEA nunmal keinen Speicher hat: Er kann nicht speichern, wie lang das Wort x ist um zu prüfen, ob y genauso lang ist.

Die Bedingung z = xy mit |x| = |y| sagt ja eigentlich nur eins aus: Das Wort z läßt sich in zwei gleichgroße Teile zerlegen. Sprich: Das Wort hat eine gerade Anzahl Zeichen. Zur Verteilung der Zeichen wird in der Bedingung gar nichts gefordert. Ein Wort könnte auch so aussehen: 011111. Und um zu testen, ob ein Wort eine gerade Anzahl Zeichen hat, muß man bei einem DEA nur zwischen den Zuständen "ungerade" und "gerade" hinundherschalten.

Viele Grüße
Carsten

Edit: Peter war schneller

This post has been edited 1 times, last edit by "Panoramix" (Aug 31st 2010, 5:49pm)


AlexL

Junior Schreiberling

  • "AlexL" is male

Posts: 222

Date of registration: Feb 10th 2008

Location: Walsrode

Occupation: Master Informatik

35

Tuesday, August 31st 2010, 9:35pm

hi, nochmal kurz zu aufg 1.4 mit der jede sprache... wieso nicht?
Alex

Spunkmeyer

Trainee

  • "Spunkmeyer" is male

Posts: 64

Date of registration: Apr 2nd 2008

Location: Wunstorf

Occupation: Programmierer

36

Tuesday, August 31st 2010, 9:45pm

Weil dazu sicher sein muss, dass die TM anhält und das ist doch nicht bei allen Sprachen der Fall. Halteproblem. (Zumindest habe ich es so verstanden)
DEADBEEF = 3735928559

FSW16

Trainee

  • "FSW16" is male

Posts: 119

Date of registration: Jun 25th 2008

Location: Hildesheim

37

Tuesday, August 31st 2010, 9:46pm

@Alex: ich nehme mal an weil es auch nicht entscheidbare Sprachen gibt (das allgemeine Halteproblem zum Beispiel) und diese lassen sich ja nicht mit einer nichtdeterministischen Turingmaschine erzeugen.
Korrigiert mich bitte wenn ich falsch liege.

MfG

Edit: Da war ich zu langsam ;)

This post has been edited 2 times, last edit by "FSW16" (Aug 31st 2010, 10:42pm)


AlexL

Junior Schreiberling

  • "AlexL" is male

Posts: 222

Date of registration: Feb 10th 2008

Location: Walsrode

Occupation: Master Informatik

38

Tuesday, August 31st 2010, 10:08pm

alles klar danke. war bisher so zuversichtlich und eben die klausur vom letzten mal angeschaut.... da wars vorbei mit "wird schon"

Peter

Praktikant

Posts: 31

Date of registration: Feb 1st 2008

39

Tuesday, August 31st 2010, 10:38pm

Zu 1.4:
Deine Antwort, FSW16, ist nicht ganz korrekt. Denn das Halteproblem ist zwar nicht entscheidbar, ist aber von einer Turingmaschine "akzeptierbar". Hierzu muss es ja bloß semi-entscheidbar sein - und das ist es.

Die Antwort auf die Aufgabe ist aber dennoch "falsch", weil es auch Sprachen gibt, die sogar nicht mal semi-entscheidbar sind, z.B. das Komplement vom Halteproblem.
Beweis dazu: Annahme, wäre semi-entscheidbar. Da auch K selbst semi-entscheidbar ist, wäre dann (dazu gab es in der Vorlesung einen Satz, das ging mit "parallel simulieren" der beiden Semi-Entscheidungs-Turingmaschinen) K sogar entscheidbar. Was aber bekanntermaßen nicht der Fall ist. QED.

Generell kann man sich merken: Eine Sprache ist "akzeptierbar" bedeutet das gleiche wie, dass sie "semi-entscheidbar" ist.
Begründung:
Akzeptierbar ist definiert als: Es gibt eine Turingmaschine, die genau bei den Wörtern aus der Sprache einen Endzustand erreicht (und dann anhält) und bei den restlichen Wörtern nie einen Endzustand erreicht (und aber ewig läuft, weil sie ja nicht gesagt bekommt, dass sie anhalten soll).
Semi-entscheidbar ist definiert als: Es gibt eine Turingmaschine, die bei den Wörtern aus der Sprache "1" ausgibt und bei allen anderen Wörtern ewig läuft.
Man muss also nur noch zeigen, dass man jede Turingmaschine so umbauen kann, dass sie, wenn sie irgendwann anhält, dann auch "1" ausgibt - und das ist leicht getan, denn sie muss ja nur das Band löschen und 1 draufschreiben, bevor sie dann schließlich anhält.

  • "Schokoholic" is male

Posts: 2,518

Date of registration: Oct 4th 2006

Location: Hannover

Occupation: Haarspaltung

40

Tuesday, August 31st 2010, 10:47pm

Akzeptierbar ist definiert als: Es gibt eine Turingmaschine, die genau bei den Wörtern aus der Sprache einen Endzustand erreicht (und dann anhält) und bei den restlichen Wörtern nie einen Endzustand erreicht (und aber ewig läuft, weil sie ja nicht gesagt bekommt, dass sie anhalten soll).
Semi-entscheidbar ist definiert als: Es gibt eine Turingmaschine, die bei den Wörtern aus der Sprache "1" ausgibt und bei allen anderen Wörtern ewig läuft.

Huch... also für mich ist es ja nicht mehr relevant, aber dieser Teil macht mich irgendwie stutzig. Wenn die beiden Begriffe wie du sagst äquivalent sind (was sofort einleuchtet), warum gibt es dann überhaupt beide? Hat das irgend einen praktischen Zweck oder ist das wirklich nur "mathematische Klugscheißerei" um Studenten zu ärgern? ;)