Czy można zadecydować o równości języka dla gramatyk liniowych bezkontekstowych?

Rozważmy dwa gramatyk bezkontekstowych i i zadać następujące pytanie: Czy , czyli są dwa równoważne gramatyki? $G_1$ $G_2$ $L(G_1) = L(G_2)$

Ogólnie problem ten jest nierozstrzygalny. Jednakże, jeśli zarówno i są liniowe lewej (lub prawej) Gramatyki liniowe, to problem jest rozstrzygalne, ponieważ obie opisują gramatyk regularnych języków. $G_1$ $G_2$

Moje pytanie dotyczy tego, czy ten sam problem jest rozstrzygalny, gdy obie gramatyki są liniowe. Ponadto, jeśli ktoś może wskazać odpowiednią literaturę, będzie to bardzo mile widziane!

W semestrze tym że jest nierozstrzygalny dla ogólnych gramatyk liniowych ( public.asu.edu/~ccolbou/src/555hw3extras16sol.pdf , pytanie 3). To tylko proste ograniczenie problemu równości.

A L L_{L G}

$ALL_{LG}$

Ryan

Odpowiedzi:

Cytując Amiram Yehudai, The Decidability of Equivalence for a Family of Linear Gramatyki , Information and Control 47, 122-136 (1980) , strona 1:

Problem równoważności dla różnych rodzin języków jest bardzo interesujący w teorii języków formalnych. Problem ten jest rozstrzygalny w przypadku zwykłych języków (Rabin i Scott, 1959) i nierozstrzygalny w przypadku języków bezkontekstowych (Bar-Hillel i in., 1961). Jest także nierozstrzygalny dla rodziny liniowych języków bezkontekstowych, jak wynika z Lemma 1 w (Baker i Book, 1974). Rodzina jednolitych języków liniowych jest naturalną i nietrywialną podrodziną języków liniowych, dla których można rozstrzygać o równoważności.

$\Sigma^*$

reinierpost
źródło

Doskonała odpowiedź! Dziękuję bardzo, będzie to bardzo przydatne w mojej pracy doktorskiej.

Sprawdziłbym dowód, gdybym był tobą, to raczej pośrednie.

reinierpost