10. Разрешимые и неразрешимые свойства кс-грамматик

10.1. Разрешимые свойства КС-грамматик

Теорема. СвойствоL(G) разрешимо для КС-грамматик.

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

Теорема. ЕслиG=<V_T,V_N,S,R> – КС, неукорачивающая грамматика, то языкL(G) разрешим, т.е. для любой цепочкиV_T* можно определить,L(G) или жеL(G).

Доказательство:

Пусть , L(G) и=n. Тогда существует вывод цепочкиI,…,,,…,, … , ,. Т.е. некоторая цепочка встречается в выводе более одного раза. Тогда, удалив из вывода фрагмент,…,,получим опять вывод цепочки.

Значит, для любого слова L(G) существует его бесповторный вывод вG, т.е. вывод, в котором все цепочки различны, причем длина каждой цепочкиn. Число таких цепочек ограничено числом

, а значит, длина вывода ограничена числомr(n)!( в принципе можно дать более точную оценку, но достаточно и этой). Откуда получается простой алгоритм распознавания нам здесьL(G) или жеL(G)?

Перебираем все бесповторные последовательности цепочек длины n, в которых каждая следующая цепочка не короче предшествующей, и проверяем, является ли она выводом в данной грамматике. Сложность такой проверки ограничена, т.к. на каждом шаге проверяем выводимостьa_i+1 изa_i. Если хоть одна последовательность является выводом требуемой цепочки, тоL(G) иначеL(G).

Теорема. ЕслиG– приведенная грамматика без цепных правил, то существуют константы с1 и с2, зависящие отG, что для любого вывода() цепочкиL(G)

c₁()c₂, где()- длина вывода цепочки.

Доказательство:

Пусть имеется грамматика G=< V_T,V_N, S, R>.

Обозначим K- V_N,L– максимальная длина правой части правила вR, т.е.L={max A R & A V_N}. Т.к.Gне содержит цепных и укорачивающих правил, то для любого вывода^K,>, значит, для выводаS^K,, следовательно,()K, с другой стороны,L(), поэтому,L(), что требовалось доказать.

Теорема.

Если G=< V_T,V_N, S, R>– КС-грамматика, тоL(G) бесконеченсуществует нетерминальный символA_iтакой, чтоS⁺XA_iY,A_i⁺ZA_iW,ZW1, иA_i⁺V&(X,Y,Z,W,V V_T*).

Доказательство:

Считаем, что рассматриваемая грамматика не содержит цепных правил.

1. Доказательство бесконечности языка при условии S⁺XA_iY,A_i⁺ZA_iW,ZW1, иA_i⁺Vочевидно, т.к. при представленных условиях фрагмент выводаA_i⁺ZA_iWможет быть включен в вывод произвольное число раз; следовательно,S⁺XVY, иS⁺XZ^jVW^jYдля всехj0,что и обеспечивает построение бесконечного множества цепочек заданного вида.

2. Пусть язык, порождаемый грамматикой, является бесконечным, а условие теоремы не выполняется. Тогда максимальная глубина (длина ветви) синтаксического дерева для цепочки, порождаемой грамматикой, не превышает  V_N. Число таких деревьев конечно, значит, конечно число цепочек, порождаемых грамматикой.

Если же язык бесконечен, то глубина деревьев не ограничена, значит, в каком-нибудь синтаксическом дереве Т существует нетерминал A_i, через который ветвь дерева проходит неоднократно, причем это дерево соответствует выводу терминальной цепочки. Значит, во-первых, существует путь из начальной вешнины в данную вершину, и в силу отсутствия цепных правил,S*A_i,*X,*Y,X,YV_T*, во-вторых, в силу выводимости изA_i терминальной цепочки,A_iVV_TV_T, в третьих, из-за повторения нетерминалаA_iв ветви дереваA_i⁺A_i,*Z,*W,Z,W V_T*, значит,A_i⁺ZA_iW,ZW1. Что и требовалось доказать.

Из доказанной теоремы следует

Следствие 1. Для КС-грамматикиG=< V_T,V_N, S, R>существуют числаp,qтакие, что для любой цепочкиL(G), еслиp, то она имеет вид=, где,q, и для любого nцепочка видаⁿⁿL(G),n0.

Следствие 2.Язык {aⁿbⁿcⁿ,n} не порождается КС-грамматикой.

Теорема. СвойствоL(G)=разрешимо для КС-грамматик.

Разрешимость свойства следует из рассмотренных ранее алгоритмов: Язык L(G) не пуст тогда и только тогда, когда начальный символ грамматики является производящим.

10.2. Неразрешимые свойства КС-грамматик.

Поскольку класс множеств (слов), порождаемых грамматиками, совпадает с классом перечислимых множеств, то для языков класса «0» справедлив аналог теоремы Райса «никакое нетривиальное свойство языков класса 0 не является алгоритмически разрешимым» (Т.е. для нетривиального свойства не существует алгоритма, который по произвольной грамматике Gвыяснял, обладает ли данным свойством языкL(G)).

Для КЗ-грамматик проблема пустоты и бесконечности неразрешимы. Для КС-грамматик эти проблемы разрешимы.

Неразрешимые проблемы для КС-грамматик следуют из неразрешимости проблемы Поста.

Формулировка этой проблемы в виде, удобном для наших целей, следующая: для двух списков цепочек X=(₁,₂,…,_m) иY=(₁,₂,…_m) в алфавитеUопределить, существует ли последовательность индексовi₁,i₂,…i_n, такая, что.

Пусть Uиmфиксированы. Введём алфавит дополнительных символовU₀={b₁,b₂,…b_m},U₀U=/

U₁=U₀U. ПустьX=(₁,₂,…,_m) –цепочки вU. ТогдаQ(X) – множество цепочек вида,n1.

Тогда для Q(X) справедливы утверждения

1. Если X=(₁,₂,…,_m) иY=(₁,₂,…_m) списки цепочек вU, то комбинаторная проблема Поста разрешима тогда и только тогда, когдаQ(X)Q(Y)=. Пусть существуетQ(X) иQ(Y). Тогда, а значит,

2. Для любого списка X=(₁,₂,…,_m) цепочек вU,Q(X) – КС-язык вU. Соответствующая КС-грамматика G=<V_T,V_N,S,R> для языкаQ(X) -G=<U₁,{I} ,I,R>;R: {Ib_iI_i,Ib_i_i}. Грамматика является однозначной.

Из введенных утверждений следует теорема:

Теорема. Не существует алгоритма, который по двум КС-грамматикамG₁иG₂определял бы,L(G₁)L(G₂)=?

Доказательство: Если бы такой алгоритм существовал, то проблема Поста была бы разрешима.

Теорема. Не существует алгоритма, который по любой КС- грамматике позволял бы определить, является ли эта грамматика однозначной.

Доказательство:

Рассмотрим множества Q(X) дляX=(₁,₂,…,_m) иQ(Y) дляY=(₁,₂,…_m). Правила грамматики для порожденияQ(X):R_X={Ab_iA_i,Ab_i_i} правила грамматики для построения множестваQ(Y):R_Y={Bb_iB_i,Bb_i_i}.

Грамматика для порождения Q(X)Q(Y)G=<U, {A,B},I,R>, гдеR=R_XR_Y{IAB}. Эта грамматика однозначна, еслиQ(X)Q(Y)=, а это свойство неразрешимо.

Другие неразрешимые проблемы для КС-языков:

1. Является ли КС-языком пересечение КС-языков?

2. Является ли КС-языком дополнение КС-языков?

3. Проблема тривиальности КС-языка L=V*(= проблеме пустоты дополнения)?

4. Проблема эквивалентности КС-грамматик.