Rozstrzygalność równości świetlówek kompaktowych

Rozstrzyga się następujący problem:

Biorąc pod uwagę bezkontekstową gramatykę , czy ? $G$ $L(G) = \varnothing$

Następujący problem jest nierozstrzygalny:

Biorąc pod uwagę bezkontekstową gramatykę , czy ? $G$ $L(G) = A^{\ast}$

Czy istnieje charakterystyka języków bezkontekstowych $M$ z rozstrzygającą równością $L(G) = M$ ?

computability fl.formal-languages

— sdcvvc
źródło

Crosspost z math.SE .

— sdcvvc

Na przykład rozstrzygalne jest, gdy jest skończone (łatwe), gdy (według twierdzenia Parikha) lub gdy (według Parikha i sprawdzania skrzyżowanie z uzupełnieniem )

M

$M$

M = {a}^{*}

$M = \{a\}^{\ast}$

M = {a^{n} b^{n}}

$M = \{a^n b^n\}$

a^{*} b^{*}

$a^{\ast} b^{\ast}$

— sdcvvc

Czy wiesz, że jeśli zbiór CFGs st jest równa jest rozstrzygalne jest rozstrzygalne sama? Jakiego rodzaju charakterystyki szukasz? Czy chcesz mieć „prostą” listę właściwości, która obejmie wszystkie przypadki?

G

$G$

L (G)

$L(G)$

— Kaveh

Myślę, że to jest dokładnie pytanie.

— domotorp

@Kaveh: Nie wiem, czy ten zbiór jest rozstrzygalny, choć wydaje się, że nie. Najlepszą odpowiedzią byłyby albo „proste” warunki obejmujące wszystkie przypadki, albo przykłady pokazujące, że zjawisko jest zbyt złożone. Jest to trochę niejasne, ale myślę, że można na nie odpowiedzieć.

— sdcvvc,

Odpowiedzi:

Nie jestem pewien, czy istnieje jakakolwiek ogólna charakterystyka równoważności, ale następujące artykuły Hopcroft, Hunt i Rosenkrantz i. może być dobry początek:

John E. Hopcroft, O problemach z równoważnością i ograniczaniem dla języków bezkontekstowych, Theory of Computing Systems 3 (2): 119-124, doi: 10.1007 / BF01746517 ;
Harry B. Hunt, III i Daniel J. Rosenkrantz, O problemach równoważności i ograniczania języków formalnych, Journal of the ACM 24 (3): 387--396, 1977, doi: 10.1145 / 322017.322020 .

Hopcroft pokazuje w szczególności, że jeśli jest regularne, to jest rozstrzygalne iff jest ograniczone, tj. Istnieje słów st . $M$ $L(G)=M$ $M$ $n$ $w_1,w_2,\ldots,w_n$ $M\subseteq w_1^\ast w_2^\ast\cdots w_n^\ast$

— Sylvain
źródło

-2

Przepraszamy za stary wątek. Ale jest coś, co może być istotne.

Niech pCFL będzie klasą świetlówek kompaktowych zamkniętych permutacją. Problem równości dla pCFL jest rozstrzygalny.

Biorąc pod uwagę w , niech . Zgodnie z twierdzeniem Parikha jest półliniowe, ilekroć jest pozbawione kontekstu. $L$ $\Sigma = \{ \sigma_1 , \dots , \sigma_n \}$ $W_L = \{ \langle \#_{a_1}(w) , \dots , \#_{a_n}(w) \rangle \mid w \in L\}$ $W_L$ $L$

Teraz, jeżeli jest w pCFL , że mamy wtw . Tak więc, dla , w pCFL , IFF . Ale równość zbiorów półliniowych jest rozstrzygalna; widzieć: $L$ $w \in L$ $\langle \#_{a_1}(w) , \dots , \#_{a_n}(w) \rangle \in W_L$ $L_1 , L_2$ $L_1 = L_2$ $W_{L_1} = W_{L_2}$

Huynh 1980 „Złożoność zestawów półliniowych”: http://link.springer.com/chapter/10.1007%2F3-540-10003-2_81#

Rodzi to pytanie, na które chciałbym poznać odpowiedź: czy można rozstrzygnąć, czy dany język bezkontekstowy jest zamknięty na permutację?

— Shane Steinert-Threlkeld
źródło

To nie jest odpowiedź na pierwotne pytanie, ale osobne (choć powiązane) pytanie. Trzeba go zapytać, jak to jest własne pytanie (z linkiem do tej kwestii) albo tutaj lub na CS.SE .

— Artem Kaznatcheev

Tak, usuń tę odpowiedź i opublikuj ją jako nowe pytanie (z linkiem do tego)

— Suresh Venkat

@SureshVenkat wygląda na to, że użytkownik pyta o to na końcu tego pytania . Więc może nowe pytanie nie jest potrzebne.

— Artem Kaznatcheev

pCFL

$\textbf{pCFL}$