Fachrat Informatik - Forum

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

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

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

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

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.

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.

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.

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

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

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.

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

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.

Ok, Danke für die Antworten

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

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)

@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

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

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.

Quoted from "Peter"

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?