Вопрос 9. Разрешимость языков. Теоремы о разрешимости языков, заданных произвольной и не укорачивающей грамматикой.
Под разрешимостью языков понимается распознавание свойств языка, по свойствам задающей её грамматики.
Теорема 1.6. Не существует эффективной процедуры, которая по произвольной грамматики типа 0, выяснила бы обладает этот язык каким-либо нетривиальным свойством.
Теорема 1.7. Если G1 — не укорачивающая грамматика, то язык L(G1) — разрешим.
Доказательство. Предположим задана ? ? L (G1) , длина конечна |?| = n. I? …?????…???…?? , I?…???…?? (??…??). Для любой строки ? существует её без повторный вывод, который имеет ограниченную длину.
?? ? L(G1) . Длина вывода не превосходит n.
r(n) — количество строк вывода. r(n) ? ?ni=1 |V?W|i .
Вопрос 10. Теорема о разрешимости проблемы пустоты КС-языка. Теорема о разрешимости проблемы бесконечности КС-языка.
Замечание. Для языков, которые порождают грамматики типа 1, неразрешимы проблемы пустоты и бесконечности языка.
Теорема 1.8. Если G2 контекстно-свободная грамматика, то разрешимы следующие проблемы: проблема пустоты языка, проблема бесконечности языка, проблема принадлежности некоторой строки языку L(G2).
Для того, чтобы язык был бесконечен, необходимо и достаточно, чтобы существовал в грамматике вывод A?G2 ? A ?.
Вопрос 11. Теорема о разрешимости языка, заданного КС-грамматикой.
Эффективная процедура разрешимости языков, порождаемых КС-грамматикой.
Шаг 0. Используем приведенную грамматику, вводим обозначение множеств терминальных строк порождаемых каждым нетерминальным знаком и составляем систему уравнений, относительно этих множеств и операции конкатенации и объединение, соответствующих продукциям грамматики.
I?AI|BI|a , A?BB|a , B?AA|b , спрашивается, принадлежит ли строка abbaba этой грамматике. Введем XI , XA , XB :
? XI = XA XI ? XB XI ? {a} {a,b}{bb} = {abb, bbb}
? XA = XB XB ? {a}
? XB = XA XA ? {b}
Шаг 1. Ищем решение системы уравнений над множествами X(1) = F(1) ( 0 ), для чего в систему уравнений подставляется X(0) = (0, 0, 0, …, 0) : XI(1) = {a} ; XA(1) = {a} ; X B(1) = {b} .
Шаг i. Пусть имеем решение системы уравнений X(i) = F(i) (0)
Шаг i+1. Ищем решение системы уравнений в виде : X(i+1) = F (Fi(0)) = Fi+1(0)
XI(2) = {aa, ba, a} ; XA(2) = {bb, a} ; Xb(2) = {aa, b}. В зависимости от вида искомой или исходной строки удаляем из полученных множеств X(i+1) все строки с длиной равной или большей, чем длина исходной строки, а также те строки, которые не являются подстроками исходной строки.
XI(2) = {ba, a} ; XA(2) = {bb, a} ; XB(2) = {b}. Если получена искомая строка в множестве соответствующем аксиоме грамматики или множества на шаге k , совпадают с множествами полученными на шаге k-1 , в этом случае строка не принадлежит языку L(G). Т.к. количество уравнений конечно и длина искомой строки конечна, то не более чем через n*m шагов, мы получили решение задачи (где n-количество уравнений, m — длина искомой строки). XI(3) = {bbba, bba, aba, aa, bba, ba, a} ; XA(3) = {bb, a} ; XB(3) = {bbbb, bba, abb, aa, b}.
XI(4) = {bbba, bbaba, bbba, bba, abba, aaba, aba, aa, bbabba, bbaaba, bbaba, bbaa, abbbba, abbaba, abbba, abba, bbba, baba, bba, ba, a} , т.о. мы решили, что эта строка принадлежит этому языку.
Теорема 1.9. Следующие проблемы, для языков порождаемых КС-грамматиками неразрешимы: 1) пустоту и пересечение двух КС — языков L(G2|) ? L(G2||) =? ? 0 ; 2) является ли КС — языком пересечение двух КС — языков. L(G2|) ? L(G2||) =? L(G2|||) ; 3) является ли КС — языком дополнение КС — языка V*\L(G2|) =? L(G2||) ; 4) эквивалентны ли 2 КС — грамматики L(G2|) =? L(G2||) ; 5) является ли произвольная КС — грамматика однозначной. (Однозначность — существование единственного вывода для каждой строки).
