Разрешимо ли языковое равенство для линейных контекстно-свободных грамматик?

Давайте рассмотрим две не зависящие от контекста грамматики и и зададим следующий вопрос: Являются ли , то есть эквивалентны ли эти две грамматики? $G_1$ $G_2$ $L(G_1) = L(G_2)$

В общем, эта проблема неразрешима. Однако, если и и являются леволинейными (или праволинейными) грамматиками, то проблема разрешима, поскольку обе грамматики описывают обычные языки. $G_1$ $G_2$

Мой вопрос заключается в том, разрешима ли одна и та же проблема, когда обе грамматики линейны. Кроме того, если кто-то может указать на соответствующую литературу, это будет высоко оценено!

В этом семестре я доказал, что

неразрешима для общих линейных грамматик ( public.asu.edu/~ccolbou/src/555hw3extras16sol.pdf , Вопрос 3). Это просто прямое сокращение проблемы равенства.

A L L_{L G}

$ALL_{LG}$

Райан

Ответы:

Цитата из Амирама Иегудаи «Разрешимость эквивалентности для семейства линейных грамматик , информация и управление», 47, 122–136 (1980) , стр. 1:

Проблема эквивалентности для различных семейств языков представляет большой интерес в теории формальных языков. Эта проблема разрешима для обычных языков (Рабин и Скотт, 1959) и неразрешима для контекстно-свободных языков (Bar-Hillel et al., 1961). Это также неразрешимо для семейства линейных контекстно-свободных языков, как следует из леммы 1 в (Baker and Book, 1974). Семейство однородных линейных языков является естественным и нетривиальным подсемейством линейных языков, для которых эквивалентность разрешима.

$\Sigma^*$

reinierpost
источник

Отличный ответ! Большое спасибо, это будет очень полезно для моей кандидатской диссертации.

Я бы проверил доказательства на вашем месте, это скорее косвенно.

reinierpost