| Autor |
 Schnitt nicht entscheidbarer Sprachen |
|
Rapha00
Aktiv 
Dabei seit: 05.12.2020
Mitteilungen: 23
 |
Guten Abend,
Ich habe in der Uni momentan folgende Fragestellung:
Für alle Sprachen $L_1$ und $L_2$ gilt: Falls $L_1$ und $L_2$ nicht entscheidbar sind, so ist auch $L_1 \cap L_2$ nicht entscheidbar.
Ich weiß, dass für entscheidbare Sprachen $L_3$ und $L_4$ gilt, dass diese auch unter Schnitt entscheidbar sind. Ich habe mir jetzt ein paar Stunden meinen Kopf darüber zerbrochen und leider finde ich weder im Skript noch im Internet einen Ansatz für diese Aufgabe.
Gilt diese Aussage? Und ja/ nein wieso?
Vielen Dank!
|
 Notiz  Profil
 Quote
 Link |
Bilbo
Senior 
Dabei seit: 03.01.2005
Mitteilungen: 1977
 |      Beitrag No.1, eingetragen 2021-01-18
|
Hallo Rapha0,
betrachte doch mal eine unentscheidbare Sprache und ihr Komplement. Was kannst Du über die Entscheidbarkeit des Komplements sagen? Und was über den Durchschnitt der beiden Sprachen und dessen Entscheidbarkeit?
Viele Grüße
Thorsten
-----------------
Heilmagier der Drachengilde
Wohlordner des Universums
Rechner des Unberechenbaren
Navigator Irrlichts im Ozean der Rätsel
|
Notiz Profil
Quote
Link |
Rapha00
Aktiv
Dabei seit: 05.12.2020
Mitteilungen: 23
| Beitrag No.2, vom Themenstarter, eingetragen 2021-01-18
|
Guten Abend!
Das Komplement einer entscheidbaren Sprache ist auch entscheidbar. Also denke ich mal, dass das Komplement einer unentscheidbaren Sprache auch unentscheidbar ist. Und da auch ein Schnitt von entscheidbaren Sprachen entscheidbar ist, ist ein Schnitt der Komplemente auch entscheidbar, oder?
|
Notiz Profil
Quote
Link |
tactac
Senior
Dabei seit: 15.10.2014
Mitteilungen: 1989
 | Beitrag No.3, eingetragen 2021-01-18
|
2021-01-18 22:24 - Rapha00 in Beitrag No. 2 schreibt:
Guten Abend!
Das Komplement einer entscheidbaren Sprache ist auch entscheidbar. Also denke ich mal, dass das Komplement einer unentscheidbaren Sprache auch unentscheidbar ist. Man kann das nicht nur "mal denken", sondern auch beweisen.
Und da auch ein Schnitt von entscheidbaren Sprachen entscheidbar ist, ist ein Schnitt der Komplemente auch entscheidbar, oder?
In Bilbos Tipp geht es um den Schnitt einer unentscheidbaren Sprache mit ihrem Komplement.
|
Notiz Profil
Quote
Link |
Rapha00
Aktiv
Dabei seit: 05.12.2020
Mitteilungen: 23
| Beitrag No.4, vom Themenstarter, eingetragen 2021-01-19
|
Das habe ich mir gedacht aber leider weiß ich nicht, was die Antwort darauf ist..
|
Notiz Profil
Quote
Link |
DerEinfaeltige
Senior
Dabei seit: 11.02.2015
Mitteilungen: 2694
 | Beitrag No.5, eingetragen 2021-01-19
|
2021-01-19 08:44 - Rapha00 in Beitrag No. 4 schreibt:
Das habe ich mir gedacht aber leider weiß ich nicht, was die Antwort darauf ist..
Was kommt denn (per definitionem) heraus, wenn man eine beliebige Menge mit ihrem Komplement schneidet?
-----------------
Why waste time learning when ignorance is instantaneous?
- Bill Watterson -
|
Notiz Profil
Quote
Link |
Rapha00
Aktiv
Dabei seit: 05.12.2020
Mitteilungen: 23
| Beitrag No.6, vom Themenstarter, eingetragen 2021-01-19
|
Notiz Profil
Quote
Link |
DerEinfaeltige
Senior
Dabei seit: 11.02.2015
Mitteilungen: 2694
| Beitrag No.7, eingetragen 2021-01-19
|
Natürlich.
Jetzt müssen wir noch überlegen, ob die leere Menge/leere Sprache entscheidbar ist.
-----------------
Why waste time learning when ignorance is instantaneous?
- Bill Watterson -
|
Notiz Profil
Quote
Link |
Rapha00
Aktiv
Dabei seit: 05.12.2020
Mitteilungen: 23
| Beitrag No.8, vom Themenstarter, eingetragen 2021-01-19
|
Laut Wikipedia ist das Leerheitsproblem für alle Grammatiken höher Typ 2 in der Chomsky-Hierarchie entscheidbar, darunter im Allgmeinen jedoch nicht. Aber in meiner Aufgabenstellung ist ja nicht angegeben, von welchem Typ die Sprachen sind.
|
Notiz Profil
Quote
Link |
tactac
Senior
Dabei seit: 15.10.2014
Mitteilungen: 1989
| Beitrag No.9, eingetragen 2021-01-19
|
Das Leerheitsproblem spielt hier keine Rolle.
|
Notiz Profil
Quote
Link |
DerEinfaeltige
Senior 
Dabei seit: 11.02.2015
Mitteilungen: 2694
| Beitrag No.10, eingetragen 2021-01-19
|
Wink mit dem Zaunpfahl:
Könnte man einen Automaten konstruieren, der entscheidet, ob ein Wort in der leeren Sprache liegt?
Das Leerheitsproblem stellt sich hier nicht. Wir wissen bereits, dass die Sprache $L\cap \overline{L} =\emptyset$ leer ist.
-----------------
Why waste time learning when ignorance is instantaneous?
- Bill Watterson -
|
Notiz Profil
Quote
Link |
Rapha00
Aktiv 
Dabei seit: 05.12.2020
Mitteilungen: 23
| Beitrag No.11, vom Themenstarter, eingetragen 2021-01-19
|
Ja, man könnte einen Automaten konstruieren, der entscheidet, ob ein Wort in der leeren Sprache liegt. Dieser akzeptiert nur, wenn das Wort das leere Wort ist. Oder?
|
Notiz Profil
Quote
Link |
Buri
Senior
Dabei seit: 02.08.2003
Mitteilungen: 46333
Herkunft: Dresden
 | Beitrag No.12, eingetragen 2021-01-19
|
2021-01-19 12:00 - Rapha00 in Beitrag No. 11 schreibt:
Ja, man könnte einen Automaten konstruieren, der entscheidet, ob ein Wort in der leeren Sprache liegt. Hi Rapha00,
die leere Sprache wird von einem Automaten erkannt, der nie akzeptiert.
Gruß Buri
|
Notiz Profil
Quote
Link |
Rapha00
Aktiv
Dabei seit: 05.12.2020
Mitteilungen: 23
| Beitrag No.13, vom Themenstarter, eingetragen 2021-01-19
|
Entschuldigung wenn ich gerade auf dem Schlauch stehe aber ich bekomme meinen Kopf gerade noch nicht wirklich um das Thema.
Wenn die leere Sprache von einem Automaten erkannt wird, der nie akzeptiert, dann ist die Sprache unentscheidbar, oder?
|
Notiz Profil
Quote
Link |
Buri
Senior
Dabei seit: 02.08.2003
Mitteilungen: 46333
Herkunft: Dresden
| Beitrag No.14, eingetragen 2021-01-19
|
2021-01-19 12:43 - Rapha00 in Beitrag No. 13 schreibt:
... dann ist die Sprache unentscheidbar, oder? Hi Rapha00,
nein.
Der niemals akzeptierende Automat entscheidet richtig.
Er akzeptiert genau die Wörter in der leeren Sprache, nämlich keine.
Gruß Buri
|
Notiz Profil
Quote
Link |
Rapha00
Aktiv
Dabei seit: 05.12.2020
Mitteilungen: 23
| Beitrag No.15, vom Themenstarter, eingetragen 2021-01-19
|
Hi,
Okay, ich glaube das habe ich verstanden.
Und wahrscheinlich ist die Antwort auf meine eingangs gestellte Frage mittlerweile offensichtlich und ich schlage mir vor die Stirn, wenn ich darauf komme. Aber wie hilft mir das jetzt bei meiner Fragestellung?
Vielen Dank.
|
Notiz Profil
Quote
Link |
tactac
Senior
Dabei seit: 15.10.2014
Mitteilungen: 1989
| Beitrag No.16, eingetragen 2021-01-19
|
\(\begingroup\)\(\newcommand{\sem}[1]{[\![#1]\!]}
\newcommand{\name}[1]{\ulcorner#1\urcorner}
\newcommand{\upamp}{\mathbin {⅋}}\)
Wenn du eine unentscheidbare Sprache $L_1$ hast, kannst du dann vielleicht eine unentscheidbare Sprache $L_2$ angeben, so dass $L_1 \cap L_2$ entscheidbar ist?\(\endgroup\)
|
Notiz Profil
Quote
Link |
Rapha00
Aktiv
Dabei seit: 05.12.2020
Mitteilungen: 23
| Beitrag No.17, vom Themenstarter, eingetragen 2021-01-19
|
Wenn der Schnitt genau die leere Sprache ist, kann ich dafür den Automaten bauen, der die leere Sprache entscheidet und habe somit eine entscheidbare Sprache.. Oder?
Edit: Die Sprache $L_2$ ist dann natürlich in diesem Fall das Komplement von $L_1$.
|
Notiz Profil
Quote
Link |
tactac
Senior
Dabei seit: 15.10.2014
Mitteilungen: 1989
| Beitrag No.18, eingetragen 2021-01-19
|
\(\begingroup\)\(\newcommand{\sem}[1]{[\![#1]\!]}
\newcommand{\name}[1]{\ulcorner#1\urcorner}
\newcommand{\upamp}{\mathbin {⅋}}\)
Ok.
Wir haben also, unter der Annahme, dass für alle unentscheidbaren $L_1, L_2$ $L_1 \cap L_2$ unentscheidbar ist, folgende Folgerungen:
1) Für alle unentscheidbaren $L$ ist $L \cap L^\complement$ unentscheidbar (das ist beinahe eine Instanz der Annahme).
2) Für alle unentscheidbaren $L$ ist $L \cap L^\complement$ (also $\emptyset$ entscheidbar (das folgt aus anderen Überlegungen).
Was fehlt jetzt noch, um einen Widerspruch zu erhalten und somit die Annahme zu widerlegen?\(\endgroup\)
|
Notiz Profil
Quote
Link |
Rapha00
Aktiv
Dabei seit: 05.12.2020
Mitteilungen: 23
| Beitrag No.19, vom Themenstarter, eingetragen 2021-01-19
|
Der Widerspruch liegt ja bereits in den beiden Aussagen.
Wenn für alle unentscheidbaren $L_1, L_2$ gelten soll, dass $L_1 \cap L_2$ auch unentscheidbar ist und mit $L_2 = \overline{L_1}$ gilt, dass $L_1 \cap L_2 = \emptyset$ ist. Dann haben wir bereits ein Beispiel gefunden, dass die obige Aussage widerlegt. Richtig?
|
Notiz Profil
Quote
Link |
Buri
Senior
Dabei seit: 02.08.2003
Mitteilungen: 46333
Herkunft: Dresden
| Beitrag No.20, eingetragen 2021-01-19
|
2021-01-19 16:05 - Rapha00 in Beitrag No. 19 schreibt:
Der Widerspruch liegt ja bereits in den beiden Aussagen. Hi Rapha00,
nicht ganz. Ein Widerspruch kommt nur zustande, wenn man außerdem noch weiß, dass es eine unentscheidbare Sprache gibt.
Gruß Buri
|
Notiz Profil
Quote
Link |
Rapha00
Aktiv
Dabei seit: 05.12.2020
Mitteilungen: 23
| Beitrag No.21, vom Themenstarter, eingetragen 2021-01-19
|
Also muss das Beispiel $L_1 \cap \overline{L_1} = \emptyset$ genannt werden, gezeigt werden, dass diese Sprache entscheidbar ist und dazu gesagt werden, dass $L_1 \cap L_2 = \emptyset$ nicht für alle unentscheidbaren $L_1, L_2$ gilt? Außerdem dann natürlich noch, dass $L_1 \cap L_2$ im Allgemeinen auch unentscheidbar ist?
|
Notiz Profil
Quote
Link |
Home / Seite ohne Frame
2021-02-25 23:40 U P
Wie unterstütze ich den Matheplaneten mit Geld?
Themenstart: 2021-01-18