Matroids Matheplanet Forum Index
Moderiert von Bilbo
Theoretische Informatik » Formale Sprachen & Automaten » Schnitt nicht entscheidbarer Sprachen
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule Schnitt nicht entscheidbarer Sprachen
Rapha00
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 05.12.2020
Mitteilungen: 23
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2021-01-18


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!



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Bilbo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.01.2005
Mitteilungen: 1978
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Rapha00
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 05.12.2020
Mitteilungen: 23
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
tactac
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 15.10.2014
Mitteilungen: 1992
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Rapha00
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 05.12.2020
Mitteilungen: 23
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, vom Themenstarter, eingetragen 2021-01-19


Das habe ich mir gedacht aber leider weiß ich nicht, was die Antwort darauf ist..



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2698
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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 -



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Rapha00
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 05.12.2020
Mitteilungen: 23
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, vom Themenstarter, eingetragen 2021-01-19


Die leere Menge.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2698
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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 -



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Rapha00
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 05.12.2020
Mitteilungen: 23
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
tactac
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 15.10.2014
Mitteilungen: 1992
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, eingetragen 2021-01-19


Das Leerheitsproblem spielt hier keine Rolle.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2698
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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 -



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Rapha00
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 05.12.2020
Mitteilungen: 23
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Buri
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 02.08.2003
Mitteilungen: 46334
Herkunft: Dresden
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Rapha00
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 05.12.2020
Mitteilungen: 23
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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?




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Buri
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 02.08.2003
Mitteilungen: 46334
Herkunft: Dresden
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Rapha00
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 05.12.2020
Mitteilungen: 23
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
tactac
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 15.10.2014
Mitteilungen: 1992
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Rapha00
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 05.12.2020
Mitteilungen: 23
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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$.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
tactac
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 15.10.2014
Mitteilungen: 1992
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Rapha00
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 05.12.2020
Mitteilungen: 23
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Buri
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 02.08.2003
Mitteilungen: 46334
Herkunft: Dresden
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Rapha00
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 05.12.2020
Mitteilungen: 23
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Rapha00 hat die Antworten auf ihre/seine Frage gesehen.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]