Ich weiß nicht wie ich diese Aufgabe lösen kann, brauche Hilfe, um diese Aufgabe zu lösen.Postest du jetzt nur noch die Aufgaben? Zu deiner Frage: Bestimmt kann das jemand und du bald auch, wenn du übst
Ja, mache ich. Ich habe meine Unterlagen nochmal geguckt aber ich verstehe noch nicht, warum L aufzählbar ist.Das wird doch bestimmt in der Vorlesung behandelt worden sein. Bist Du das, was da behandelt wurde, noch mal durchgegangen? Und wenn Du Probleme hast, dem Stoff zu folgen: Es gibt zu den Themen auch meist gute Bücher, die man parallel zu den Vorlesungen lesen kann zum besseren Verständnis.
Denn es ist ja ein generelles Problem. Du solltest also auch überlegen, wie Du deine generelle Herangehensweise so anpassen kannst, dass Du die Vorlesungsinhalte verstehst.
Was muss denn gelten, damit L aufzählbar ist?Ich habe meine Unterlagen nochmal geguckt aber ich verstehe noch nicht, warum L aufzählbar ist.
{b}*
bedeutet die Anwendung des Kleeneschen Sterns/Operators und heißt hier einfach nur: Eine beliebige (auch leere) Menge von Konkatenationen des Zeichens "b", also: {b}*
= {"", "b", "bb", "bbb", "bbbb", ...}.Ich kenne alle Bedeuteung von Notation aber ich weiß nicht, wie ich es beweisen sollZuerst einmal können wir ja die Notation klären, um überhaupt zu verstehen, was hier bewiesen werden muss:
L = { ... }
Das ist in diesem Fall die Definition einer Sprache als Menge von Wörtern, die Teil der Sprache sind.
Die geschweiften Klammern sind also eine "Mengendefinition".
In diesem konkreten Fall ist aber die Tatsache, dass eine "Sprache" aus "Wörtern" besteht, gar nicht so wichtig oder entscheidend. Wichtig hier ist, dass wir die Definition einer Menge haben und eine Beschreibung, welche Elemente alle Teil dieser Menge sind. Rein mathematisch gesprochen.
Das <M> mit den etwas gestreckten Klammern ist ein Turing-Maschinen-Programm.
Der Senkrechtstrich bzw. Bar bzw. Pipe bedeutet: "für das gilt: ...".
{b}*
bedeutet die Anwendung des Kleeneschen Sterns/Operators und heißt hier einfach nur: Eine beliebige (auch leere) Menge von Konkatenationen des Zeichens "b", also:{b}*
= {"", "b", "bb", "bbb", "bbbb", ...}.
Dass das jetzt "b" sein soll oder auch nur eine beliebig häufige Konkatenation von "b" ist hier aber auch eher irrelevant. Viel wichtiger ist, was jetzt damit gemacht wird:
Das umgedrehte "U" Zeichen bedeutet "Schnittmenge" und L(M) bedeutet "Die Sprache, die durch die bereits erwähnte Turingmaschine 'M' akzeptiert wird". Das durchgestrichene Gleichheitszeichen bedeutet dann noch "ungleich" (hier ist von der Ungleichheit zweier Mengen die Rede). Und die durchgestrichene Null soll die leere Menge bedeuten.
Also, alles nochmal in einem Satz: "L ist die Menge aller Turingmaschinen 'M', für die gilt, dass die Sprache {b}* (also Menge von Wörtern mit einer beliebigen Konkatenation von "b") eine Teilmenge der von 'M' akzeptierten Sprache (L) ist." Ob die Teilmenge echt oder unecht ist, wissen wir hier nicht.
Kleiner Hinweis: Wir können aber "echt" annehmen.
Die Tatsache, dass hier derselbe Buchstabe "L" sowohl für die Definition der Menge insgesamt benutzt wird als auch als Teil dieser Definition mit L(M) ist zwar unglücklich, gemeint sind hier aber zwei verschiedene L's , also zwei verschiedene Mengen.
Insgesamt ist die Definition von L hier der Satz von Rice, nur etwas anders ausgedrückt.
Im Grund wie bei einem mathematischen Beweis: was ist gegeben, was ist gesucht, auf welche bewiesenen Aussagen / Theorien kann man sich (im Idealfall 100%-ig) verlassen ? Dann wird umgeformt bis die Aussage erbracht ( und bewiesen) ist.wie ich es beweisen soll
Anfang: s.. #7Ich kenne alle Bedeuteung von Notation aber ich weiß nicht, wie ich es beweisen soll
Das ist meine Lösung, ist es richtig?Zuerst einmal können wir ja die Notation klären, um überhaupt zu verstehen, was hier bewiesen werden muss:
L = { ... }
Das ist in diesem Fall die Definition einer Sprache als Menge von Wörtern, die Teil der Sprache sind.
Die geschweiften Klammern sind also eine "Mengendefinition".
In diesem konkreten Fall ist aber die Tatsache, dass eine "Sprache" aus "Wörtern" besteht, gar nicht so wichtig oder entscheidend. Wichtig hier ist, dass wir die Definition einer Menge haben und eine Beschreibung, welche Elemente alle Teil dieser Menge sind. Rein mathematisch gesprochen.
Das <M> mit den etwas gestreckten Klammern ist ein Turing-Maschinen-Programm.
Der Senkrechtstrich bzw. Bar bzw. Pipe bedeutet: "für das gilt: ...".
{b}*
bedeutet die Anwendung des Kleeneschen Sterns/Operators und heißt hier einfach nur: Eine beliebige (auch leere) Menge von Konkatenationen des Zeichens "b", also:{b}*
= {"", "b", "bb", "bbb", "bbbb", ...}.
Dass das jetzt "b" sein soll oder auch nur eine beliebig häufige Konkatenation von "b" ist hier aber auch eher irrelevant. Viel wichtiger ist, was jetzt damit gemacht wird:
Das umgedrehte "U" Zeichen bedeutet "Schnittmenge" und L(M) bedeutet "Die Sprache, die durch die bereits erwähnte Turingmaschine 'M' akzeptiert wird". Das durchgestrichene Gleichheitszeichen bedeutet dann noch "ungleich" (hier ist von der Ungleichheit zweier Mengen die Rede). Und die durchgestrichene Null soll die leere Menge bedeuten.
Also, alles nochmal in einem Satz: "L ist die Menge aller Turingmaschinen 'M', für die gilt, dass die Sprache {b}* (also Menge von Wörtern mit einer beliebigen Konkatenation von "b") eine Teilmenge der von 'M' akzeptierten Sprache (L) ist." Ob die Teilmenge echt oder unecht ist, wissen wir hier nicht.
Kleiner Hinweis: Wir können aber "echt" annehmen.
Die Tatsache, dass hier derselbe Buchstabe "L" sowohl für die Definition der Menge insgesamt benutzt wird als auch als Teil dieser Definition mit L(M) ist zwar unglücklich, gemeint sind hier aber zwei verschiedene L's , also zwei verschiedene Mengen.
Insgesamt ist die Definition von L hier der Satz von Rice, nur etwas anders ausgedrücd
Sei für jede Turingmaschine M die Turingmaschine B(M) gegeben durch: Für jedes n ∈ ℕ0 akzeptiert B(M) das Wort bn genau dann, wenn M ein Wort der Länge n akzeptiert.Zuerst einmal können wir ja die Notation klären, um überhaupt zu verstehen, was hier bewiesen werden muss:
L = { ... }
Das ist in diesem Fall die Definition einer Sprache als Menge von Wörtern, die Teil der Sprache sind.
Die geschweiften Klammern sind also eine "Mengendefinition".
In diesem konkreten Fall ist aber die Tatsache, dass eine "Sprache" aus "Wörtern" besteht, gar nicht so wichtig oder entscheidend. Wichtig hier ist, dass wir die Definition einer Menge haben und eine Beschreibung, welche Elemente alle Teil dieser Menge sind. Rein mathematisch gesprochen.
Das <M> mit den etwas gestreckten Klammern ist ein Turing-Maschinen-Programm.
Der Senkrechtstrich bzw. Bar bzw. Pipe bedeutet: "für das gilt: ...".
{b}*
bedeutet die Anwendung des Kleeneschen Sterns/Operators und heißt hier einfach nur: Eine beliebige (auch leere) Menge von Konkatenationen des Zeichens "b", also:{b}*
= {"", "b", "bb", "bbb", "bbbb", ...}.
Dass das jetzt "b" sein soll oder auch nur eine beliebig häufige Konkatenation von "b" ist hier aber auch eher irrelevant. Viel wichtiger ist, was jetzt damit gemacht wird:
Das umgedrehte "U" Zeichen bedeutet "Schnittmenge" und L(M) bedeutet "Die Sprache, die durch die bereits erwähnte Turingmaschine 'M' akzeptiert wird". Das durchgestrichene Gleichheitszeichen bedeutet dann noch "ungleich" (hier ist von der Ungleichheit zweier Mengen die Rede). Und die durchgestrichene Null soll die leere Menge bedeuten.
Also, alles nochmal in einem Satz: "L ist die Menge aller Turingmaschinen 'M', für die gilt, dass die Sprache {b}* (also Menge von Wörtern mit einer beliebigen Konkatenation von "b") eine Teilmenge der von 'M' akzeptierten Sprache (L) ist." Ob die Teilmenge echt oder unecht ist, wissen wir hier nicht.
Kleiner Hinweis: Wir können aber "echt" annehmen.
Die Tatsache, dass hier derselbe Buchstabe "L" sowohl für die Definition der Menge insgesamt benutzt wird als auch als Teil dieser Definition mit L(M) ist zwar unglücklich, gemeint sind hier aber zwei verschiedene L's , also zwei verschiedene Mengen.
Insgesamt ist die Definition von L hier der Satz von Rice, nur etwas anders ausgedrückt.
Ist meine Lösung richtig?Kann jemand es beweisen, warum L aufzählbar ist aber nicht entscheidbar?Anhang anzeigen 18452