Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
274 НЕРАЗРЕШИМЫЕ АЛГОРИТМИЧЕСКИЕ ПРОБЛЕМЫ [ГЛ,
Теперь для некоторых инвариантных свойств ОБ грамматик легко доказать нераспознаваемость.
Теорема 8.4. Пусть V — произвольный словарь содержащий не менее двух символов, Е — произвольно непустое множество натуральных чисел и аЕ — свойств языка в словаре V иметь дополнение (до У*), число эле:: ментов которого конечно и является элементом Е. Тогд ал нераспознаваемо в классе линейных ОЪ-граммати и тем более в классе всех ОЪ-грамматик с основны_ словарем V.
Доказательство. Для произвольной ДЭ-машин М мощность множества Н(М) равна мощности F(M)f а эта последняя — мощности области определени вычисляемой данной машиной функции. Поэтому к проблеме распознавания аЕ сводится проблема распознавания свойства машины М вычислять функцию *), область определения которой имеет конечную мощност являющуюся элементом Е.
Следствие^ 1. Следующие свойства языков нераспознаваемы в классе линейных (и тем более всех) ОЬ-грамматик с заданным основным словарем мощности, большей или равной 2:
а) иметь конечное дополнение;
б) иметь дополнение, состоящее в точности из за, данного конечного числа элементов (в частности, пу стое)
Действительно, для пункта а) достаточно взят в качестве Е множество всех натуральных чисел, дл пункта б) — множество, состоящее из одного числа.
Следствие 2. Не существует алгоритма, позволяющего для любой ОЪ-грамматики (или даже для лю бой линейной ОЪ-грамматики) с данным основным словарем мощности, большей или равной 2, распознать,, эквивалентна ли она заданной грамматике, порождаю-’ щей V*. Тем более неразрешима общая проблема эквивалентности ОЪ-грамматик..............
Следствие 3. Не существует алгоритма, позво ляющего для любых двух ОЪ-грамматик 1\ и Г2 с дан-
*) Точнее следовало бы говорить о машинах с некоторым фиксированным входным алфавитом и о проекции функции на некоторый фиксированный алфавит (ср. сноску на стр. 264). • ;
§ 3 4] ПРОБЛЕМЫ, СВЯЗАННЫЕ С Б-ГРАММАТИКАМИ ' 275
ным основным словарем мощности., большей или равной 2, распознать, содержится ли L(Ti) в ?(Гг).
В самом деле, по предыдущему следствию такой алгоритм невозможен даже для фиксированной грамматики Гь если она порождает V*.
Замечание. Ограничение на мощность словаря в теореме 8.4 и ее следствиях существенно (см. упражнение 8.16).
Для доказательства нераспознаваемое™ ряда других свойств мы воспользуемся следующей теоремой.
Теорема 8.5. Пусть U, V — словари такие, что U П V = 0, \i(V)~^2, и — класс ОЪ-грамматик, содержащий все линейные ОЪ-грамматики и такой, что соответствующий класс 3? эффективно замкнут относительно объединения и относительно умножения слева на U* и справа на V*. Тогда всякое свойство языков, нетривиальное в Я?(?Ги), справедливое для U*V* и сохраняющееся при операциях пересечения с А-языком и проектирования, нераспознаваемо в uuv- При этом сохранение свойства при проектировании может быть заменено более слабым требованием: если L s U*, у <=V* и язык Ly обладает данным свойством, то им обладает и язык L.
Доказательство. Пусть а — свойство языков, удовлетворяющее описанным условиям. В силу одного из этих условий должен существовать язык L0ei? (!Ги), не обладающий свойством а. Для произвольного языка L^2,{3TV) положим L' = U*L U L0V*. Если при этом Z, = V*, то L' — U*V*, так что а справедливо длЯ L'. Если же ЬФ V*, то, фиксировав цепочку у е V* — L и допустив, что свойство а имеет место для U, получим ввиду условий, наложенных на а, что этим свойством должен обладать и язык L' П U*y = L0y, а значит, и Пр[7(?0г/) = L0, что неверно. Таким образом, L' обладает свойством а тогда и только тогда, когда L = V*. А это позволяет заключить, — поскольку L' строится по L эффективно, — что проблема распознавания совпадения языка класса 9? (Ту) с V* сводится к проблеме распознавания а в классе 17~v\]v• Но свойство совпадать с V* нераспознаваемо в %Гv (следствие 1 из теоремы 8.4, пункт б)).
276 НЕРАЗРЕШИМЫЕ АЛГОРИТМИЧЕСКИЕ ПРОБЛЕМЫ [ГЛ. 8
Следствие. Следующие свойства языков нераспознаваемы в классе ОЪ-грамматик с заданным основным словарем мощности, большей или равной 4: (а) быть однозначным Ъ-языком; (р) быть детермини рованным языком (т. е. допускаться детерминированной МП-машиной); (у) иметь бесконтекстное дополнение; (?) быть ОА-языком\ (е) быть линейным языком; (?) быть металинейным языком-, (ti) быть итерационнолинейным языком; (0) быть ОАЕВ-языком. Свойства
(а) — (ti) нераслознаваемы также в классе ОБ-ОАЕВл грамматик, свойства (а) — (?) и (0) — в классе итерационно-линейных грамматик, свойства (а) — (е) — в классе металинейных грамматик, свойства (а)— (б) — в клас~ се линейных грамматик (при том же ограничении на словарь).
В самом деле, все перечисленные классы грамматик дают классы языков, эффективно замкнутые относи тельно нужных операций (теорема 4.8, замечания Не, стр. 170, лемма 5.1); справедливость названных свойств5 для LJ*V* очевидна, сохранение свойства (б) при нужных операциях обеспечивается теоремой 5.4, сохранение свойств (е) — (0) — замечаниями 2 и 3 в конц § 5.4, нетривиальность свойств (а) — (0) в соответствую-; щих классах при д ([/):> 2 — примерами из § 4.4 (для
