reguläre Sprachen entscheidbar?

Wissenschaft Informatik
#1

Hallo. Es seien L1, L2, L3 regülare Sprachen
Ich soll nun die Frage klären, ob L1 vereinigt L2 = L3 entscheidbar ist
Ich weiss, dass L1 geschnitten L2 = leer
und
L1 = L2 entscheidbar ist.
Jetzt frage ich mich, wie ich
L1 vereinigt L2 = L3
nachweisen kann.

Das ist sicherlich pure Mengenlehre, die ich leider nicht wirklich gut beherrsche.
(L1 vereinigt L2)c = L3c

wobei c das Komplement meint

(L1c geschnitten L2c) = L3c

Jetzt gilt (oben hatte ich es gesagt) L1 geschnitten L2 = leer ist entscheidbar, also ist
L1c geschnitten L2c
entscheidbar. Würde ich so folgern, aber kann es nicht begründen? Stimmt das? Falls ja, dann würde ich mich über eine Erklärung sehr freuen.

L1c geschnitten L2c = L4

und dementsprechend

L4 = L3c entscheidbar

Kann das hinkommen?

Gruß von McMike

#2

Hallo,

vielleicht helfen Dir diese Links:

http://de.wikipedia.org/wiki/Regul%C3%A4re_Sprache
und
http://de.wikipedia.org/wiki/%C3%84quivalenzproblem

Hier ist noch eine Zusammenfassung vom PL und dem Nachweis der Abschlusseigenschaften (auch der Vereinigung):
http://www-fs.informatik.uni-tuebingen.de/lehre/ss05…

Das sollte Dir reichen, wenn es nur um die Entscheidbarkeit geht.

Gruß,
Tobias

#3

Hilft leider nicht
Hi.

vielleicht helfen Dir diese Links:

http://de.wikipedia.org/wiki/Regul%C3%A4re_Sprache
und
http://de.wikipedia.org/wiki/%C3%84quivalenzproblem

Hier ist noch eine Zusammenfassung vom PL und dem Nachweis der
Abschlusseigenschaften (auch der Vereinigung):
http://www-fs.informatik.uni-tuebingen.de/lehre/ss05…

Die ersten beiden hatte ich schon gut durchgearbeitet. Die Powerpointpräsentation war allerdings interessant. Leider habe ich diese Beispiele alle schon gesondert gefunden, als ich mit mit dem Pumpinglemma beschäftigt habe.

Das sollte Dir reichen, wenn es nur um die Entscheidbarkeit
geht.

Nein. Das hat es mir leider nicht.
Ich kann jetzt nicht einmal folgern, ob mein Ansatz totaler Mist war oder nicht.

Kannst du da noch einmal genauer helfen?

Gruß
McMike

#4

Hi.

[…]

Kannst du da noch einmal genauer helfen?

Gruß
McMike

Hallo,

was willst Du denn genau machen? Die Entscheidbarkeit der Aquivalenz von regulären Sprachen folgt aus deren Abschlusseigenschaften und der Entscheidbarkeit des Leerheitsproblems. Das beantwortet Deine ursprüngliche Frage. Wie Du konkret den Nachweis führst hängt davon ab, welches vorwissen Du voraussetzt. Ist zum Beispiel die Entscheidbarkeit des Leerheitsprobelms gegeben, oder muss diese als Grundlage bewiesen werden. Genauso die Abschlusseigenschaften.
Dein Ansatz ist soweit OK, wenn Du die an der „norm“-Weg halten willst , startes Du mit dem Ansatz, den Du hier http://de.wikipedia.org/wiki/%C3%84quivalenzproblem findest und definierst Deie Substitutionen entsprechend.

Gruß,
Tobias