Разрешимость равенства КЛЛ

Следующая проблема разрешима:

Имеет ли контекстная грамматика , ?$G$$L(G) = \varnothing$

Следующая проблема неразрешима:

Имеет ли контекстно-свободная грамматика $G$ , $L(G) = A^{\ast}$ ?

Существует ли характеристика контекстно-свободных языков $M$ с разрешимым равенством $L(G) = M$ ?

Я не уверен, что существует какая-либо общая характеристика эквивалентности, но следующие статьи Хопкрофта, Ханта и Розенкранца соответственно. может быть хорошим началом:

• Джон Э. Хопкрофт, О проблемах эквивалентности и локализации для контекстно-свободных языков, Теория вычислительных систем 3 (2): 119-124, doi: 10.1007 / BF01746517 ;
• Гарри Б. Хант, III, и Даниэль Дж. Розенкранц, «Об эквивалентности и проблемах содержания для формальных языков», журнал ACM 24 (3): 387–396, 1977, doi: 10.1145 / 322017.322020 .

В частности, Хопкрофт показывает, что если регулярно, то разрешимо тогда и только тогда, когда ограничено, т. Существует слов 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$

Извините, что поднял старую ветку. Но вот кое-что, что может быть актуально.

Пусть pCFL - класс замкнутых по перестановке КЛЛ. Проблема равенства для pCFL разрешима.

Учитывая в , пусть . По теореме Париха является полулинейным всякий раз, когда зависит от контекста.$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$

Теперь, если находится в pCFL , у нас есть если . Таким образом, для в pCFL ,$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 "Сложность полулинейных множеств": http://link.springer.com/chapter/10.1007%2F3-540-10003-2_81#

Возникает вопрос, на который я хотел бы знать ответ: можно ли решить, является ли данный контекстно-свободный язык замкнутым?