1. Алфавит, слова, операции над словами

Вид материала

Документы

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

Подобный материал:

• Исполнительный кодекс Республики Молдова, 2184.07kb.
• Статьи 4 изложить в следующей редакции: "Статья Ответственность физических, юридических,, 41.3kb.
• Республика Молдова, 777.62kb.
• Федеральный закон, 404.04kb.
• Подготовка к операции по прорыву блокады проводилась в глубокой тайне, 18.04kb.
• Игра «Алфавит» Чтобы узнать тему нашего занятия вы должны расшифровать слова. (зашифрованные, 50.79kb.
• «День культуры и славянской письменности», 78.75kb.
• Выполнили: Фурманова Диана 3класс, 121.65kb.
• Работа со словами с непроверяемыми написаниями, 134.51kb.
• Календарно-тематический план учебная дисциплина: «Математика», 34.71kb.

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⁺ X A_i Y, A_i⁺ Z A_iW, ZW 1, и A_i⁺ V&(X,Y, Z, W,V V_T*).

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

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

1. Доказательство бесконечности языка при условии S⁺ X A_i Y, A_i⁺ Z A_iW, ZW 1, и A_i⁺ V очевидно, т.к. при представленных условиях фрагмент вывода A_i⁺ Z A_iW может быть включен в вывод произвольное число раз; следовательно, S⁺ X VY, и S⁺ X Z^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⁺ Z A_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_i I _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_i A _i, Ab_i _i } правила грамматики для построения множества Q(Y): R_Y={ Bb_i B _i, Bb_i _i }.

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

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

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

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

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