Unentscheidbare Probleme bzgl CFGs

Generelle Diskussionen zu den Themen aus der Vorlesung

Unentscheidbare Probleme bzgl CFGs

Beitragvon Franziska.Mueller » 11 Feb 2014, 20:58

Hallo zusammen,

wir hatten in der Vorlesung 4 Probleme bezüglich CFGs kennengelernt, die unentscheidbar sind:
- L(G) = \Sigma* ?
- L(G1) n L(G2) = \emptyset ?
- L(G1) \subseteq L(G2) ?
- L(G1) = L(G2) ?

Sind diese Probleme alle wüst? Falls nein, welche Teilprobleme sind akzeptierbar?
(Auf einem Test wurde nämlich auch nach Akzeptierbarkeit und nicht Entscheidbarkeit gefragt...)

Liebe Grüße,
Franziska
Franziska.Mueller
 
Beiträge: 2
Registriert: 22 Okt 2013, 23:31

Re: Unentscheidbare Probleme bzgl CFGs

Beitragvon Markus.Bauer » 11 Feb 2014, 21:18

Interessante Frage!

Relativ sicher kann ich sagen, dass L(G) = \Sigma* nicht wüst ist. Einen Akzeptor für das Gegenteil könnte man etwa so konstruieren:
Code: Alles auswählen
int i = 0;
while (true){
  foreach (x aus Sigma^i){
    if (! CYK(G,x)) return true; // Lecture 27, der Algorithmus entscheidet im Prinzip, ob x in G ableitbar ist, also x in L(G).
  }
  i++;
}

Wenn L(G) = Sigma* terminiert der Akzeptor nie, sonst wird er früher oder später akzeptieren.

Edit:
Für das Gegenteil der zweiten Menge könnte man ähnlich einen Akzeptor konstruieren, indem man für alle Elemente aus Sigma* testet, ob sie in L(G1) und L(G2) sind. Wenn ja akzeptiert man, da dann die Schnittmenge nicht leer ist.

Edit 2:
Wenn ich länger drüber nachdenke, könnte man mit dem Argument auch das Gegenteil der beiden letzten akzeptieren. Damit wären alle Sprachen dann unentscheidbar und nicht akzeptierbar, aber nicht wüst.
Markus.Bauer
 
Beiträge: 1
Registriert: 16 Okt 2013, 14:26

Re: Unentscheidbare Probleme bzgl CFGs

Beitragvon tobias.blass » 11 Feb 2014, 21:39

Hi,
eigentlich ist höchstens das dritte Problem wüst, bei den anderen ist das Komplement jeweils akzeptierbar. Ich werde jetzt keinen Akzeptor im Programmiersystem angeben (das wäre denke ich recht aufwändig) sondern nur kurz die Idee formulieren wie man bei den anderen 3 Sprachen jeweils das Komplement akzeptieren kann.

* L(G) != Sigma*
Man hat also eine Grammatik gegeben und will herausfinden ob es irgendein Wort gibt dass nicht generiert wird. Dazu iteriert man über die Länge des Wortes n. Für jedes n macht
man folgendes:
- generiere eine Liste mit allen möglichen Wörtern der Länge n
- prüfe für jedes Wort der Liste ob es akzeptiert wird (geht mit CKY)
Wenn die Grammatik irgendein Wort nicht produziert dann terminiert dieser Algorithmus irgendwann (er geht ja alle möglichen Wörter durch, also muss er irgendwann das nicht
erzeugte Wort finden) => Die Sprache wird akzeptiert. Sollte G jetzt natürlich Sigma* erzeugen dann terminiert dieser Algorithmus nie (deshalb ist das Problem unentscheidbar).

* L(G1) \cap L(G2) != {}
Prinzipiell dieselbe Idee wie vorher. Iteriere über n, zähle für beide Sprachen jeweils alle Wörter der Länge n auf die generiert werden und vergleiche die Listen. Wenn der Schnitt nicht leer ist dann wird es irgendein n geben bei dem ein Wort in beiden Listen vorkommt => das Problem ist akzeptierbar

* L(G1) != L(G2) geht dazu analog, nur dass man jetzt eben ein Wort sucht das nicht in beiden Listen vorkommt.

Beim dritten Problem glaube ich dasses wüst ist, mir fällt aber momentan keine passende Reduktion ein. Da wir die Unentscheidbarkeit der von dir genannten Probleme aber sowieso nicht bewiesen haben sollte das nicht tragisch sein. Mir fällt jedenfalls zumindest mal kein Algorithmus ein.

EDIT: ich glaube das dritte Problem ist doch nicht wüst. Um zu zeigen dass L(G1) nicht Teilmenge von L(G2) ist muss man ja nur ein einziges Wort finden dass nicht in L(G2) ist. Da kann man natürlich dieselbe Technik anwenden. Ich hatte vorhin kurz gedacht dass das Komplement L(G2) \subset L(G1) ist, was natürlich Blödsinn ist

Gruß
Tobias
tobias.blass
 
Beiträge: 3
Registriert: 17 Okt 2013, 00:38

Re: Unentscheidbare Probleme bzgl CFGs

Beitragvon Franziska.Mueller » 11 Feb 2014, 21:41

Vielen Dank für die Antworten :)
Franziska.Mueller
 
Beiträge: 2
Registriert: 22 Okt 2013, 23:31


Zurück zu Vorlesung

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 0 Gäste

cron