L(G) = {} entscheidbar?
-
Hallo leute!
Ist die Sprache L = {G | L(G) = {}} wobei G eine Grammatik ist, entscheidbar?
Ich würde sagen nein, denn:
Zu jeder Grammatik lässt sich eine Turingmaschine berechnen und umgekehrt. Seien deshalb:
S = {überall undefinierte Funktion}
T = Menge aller Turingmaschinen TM mit L(TM) = {}
T ist ja äquivalent zu dem obigen L.jetzt Reduktion definieren:
C(S) ≤ Twobei f(p) = p
Es gilt jetzt
p in (CS) => p akzeptiert keine Eingabe => f(p)=p in T
p notin C(S) => p akzeptiert mind eine Eingabe => L(p) ≠ {} => f(p) = p notin Tsomit gilt:
p in C(S) <=> f(p) in Tda nach Satz v. Rice C(S) nicht entscheidbar, ist T nicht entscheidbar und somit L.
ist dieser Beweis korrekt?
danke!
Gruß mathik
-
-