Ist die Sprachgleichheit für lineare kontextfreie Grammatiken entscheidbar?

Betrachten wir zwei kontextfreie Grammatiken und und stellen Sie die folgende Frage: Ist , sind die beiden Grammatiken äquivalent? $G_1$ $G_2$ $L(G_1) = L(G_2)$

Im Allgemeinen ist dieses Problem nicht zu entscheiden. Wenn jedoch sowohl als auch (oder rechtslineare) Grammatiken sind, ist das Problem entscheidbar, da beide Grammatiken reguläre Sprachen beschreiben. $G_1$ $G_2$

Meine Frage ist, ob das gleiche Problem entscheidbar ist, wenn beide Grammatiken linear sind. Auch wenn jemand auf relevante Literatur verweisen kann, wird das sehr geschätzt!

Ich habe in diesem Semester als TA bewiesen, dass für allgemeine lineare Grammatiken unentscheidbar ist ( public.asu.edu/~ccolbou/src/555hw3extras16sol.pdf , Frage 3). Es ist nur eine einfache Reduktion auf das Gleichstellungsproblem.

A L L_{L G}

$ALL_{LG}$

Ryan

Antworten:

Zitat aus Amiram Yehudai, Die Entscheidbarkeit der Äquivalenz für eine Familie linearer Grammatiken , Information und Kontrolle 47, 122-136 (1980) , Seite 1:

Das Äquivalenzproblem für verschiedene Sprachfamilien ist für die Theorie der formalen Sprachen von großem Interesse. Dieses Problem ist für reguläre Sprachen (Rabin und Scott, 1959) und für kontextfreie Sprachen (Bar-Hillel et al., 1961) nicht zu entscheiden. Es ist auch für die Familie der linearen kontextfreien Sprachen unentscheidbar, wie aus Lemma 1 in (Baker and Book, 1974) hervorgeht. Die Familie der einheitlichen linearen Sprachen ist eine natürliche und nichttriviale Unterfamilie der linearen Sprachen, für die die Gleichwertigkeit entscheidend ist.

$\Sigma^*$

reinierpost
quelle

Hervorragende Antwort! Vielen Dank, dies wird sehr nützlich für meine Doktorarbeit sein.

Ich würde den Beweis überprüfen, wenn ich du wäre, das ist eher indirekt.

Reinierpost