Гладкий - Формальные грамматики и языки - 1973 (947381), страница 53
Текст из файла (страница 53)
Доказательство. Пусть Л„ЛИ Л2 — НСграмматнки, порождающие 1.8, 1,1, 1., соответственно, рбл неРАВРешимые АлГОРитмические пРОБлемы [Гл, Фиксирован символы а и Ь, рассмотрим произвольну ДЭ-машину М с входным алфавитом (а) и построим дл нее НС-грамматики Г[ и Гм по лемме 8.2. Затем, прис менив к грамматикам (т) и Г" ,лемму 8.3, построим НС-грамматику Г', порождающую множество тех цепо чек из Е„для которых в Е(ГИ)) имеются цепочки рав. ной.длины, и аналогичную НС-грамматику Г" построи для (Аэ и Гт. Если вычисляемая машиной М функция определена для значения аргумента, равного а, т языки Е(Г') и Е(Г") будут, очевидно, совпадать соот ветственно с Е) ' и Ет', где по — число из леммы 8.
(по (пв в противном случае будет Е(Г')=1.), Е(Г")= Я. На. конец, построим НС-грамматику Г, порождающую язы Е(Го)() 1. (Г')),)Е (Г") (теорема 3.4). Язык 1. (Г) будет со' впадать с Ео() Е) () Ет ), если 1 определена для а, с Е,() Е, в противном случае. Но Ео() Е,ен Ы' Ео () Е(("') () Еэ("н Ф й;; таким образом, неразрешимая и теореме 8.2 проблема распознавания свойства ДЭ-ма шины М с входным алфавитом (а) вычислять функ цию *), определенную для значения аргумента а, сво дится к проблеме распознавания свойства НС-трам. матнки порождать язык, принадлежащий классу Ы 3 а м е ч а н не.
Из доказательства леммы 8.4 ясно' что она остается справедливой и в несколько усиленно формулировке; именно, для произвольного словаря свойство принадлежать классу 2' нераспознаваем ' в классе НСю То же верно и для последующих рассмот рений этого параграфа (исключая одну специальну[ проблему, особо оговариваемую ниже, стр.
267), Теперь мы можем перейти к основной теореме этог параграфа. Скажем, что языки Е) и Еэ и о ч т и с о в и'а д а ю т если они отличаются друг от друга лишь конечным чис лом элементов, т. е. их симметрическая разност' (Е) — 1.э) () (Еэ — Е,) конечна. Отношение почти совпаде ния является, очевидно, эквивалентностью; классы инду цируемого этой эквивалентностью разбиения мы будем на ') Собственно говоря, речь должна идти о проекции этой фун ции на некоторый влфввит (который можно выбрать проиэвольио)' но проектирование не изменяет области определения функции. в вэ[ ИНВАРИАНТНЫЕ СВОЙСТВА НС-ГРАММАТИК 265 зывать пучками.
Ясно, что всякий пучок, содержащий хотя бы один НС-язык, целиком состоит из НС-языков. Теорем а 8.3. Если 2' — класс языков, содержащий хотя бы один НС-язык и имеющий «отя бы с одним пучком НС-языков конечное (в частном случае пустое) пересечение, то свойство принадлежать классу .У нераспознаваемо в классе НС-грамматик. Д о к а з а т е л ь от в о. Пусть сначала пересечение Ы с пучком конечных языков бесконечно. Тогда существует пучок П, состоящий из бесконечных языков и пересекаюшийся с 2' по конечному множеству. Обозначим через Ео произвольный конечный язык, принадлежаший Ы, через Е, — пустой язык и через Š— произвольный язык из П.
При любом Гп=1,2, ... язык Ео()Е("') также принадлежит П, и, следовательно, найдется такое р, что ни при каком и ) р язык Ео () Е(") не принадлежит .У. Положив Е~~~=Е„будем иметь Ет~=Е~"~, если и) р, и Е(") = Е~~~, если и < р; поэтому при любом а=1, 2,... получаем Ео() Е()") () Е~в") = Ев() Ет('"'"("' Р)) йй й:.
В то же время Ео() Е, =Евген'. Остается применить лемму 8.4. Пусть теперь 'Р пересекается с пучком конечных языков по конечному множеству. Если прн этом .У не содержит бесконечных НС-языков, воспользуемся леммой 8.4, взяв в качестве Ео произвольный конечный язык, принадлежащий .У, в качестве Е) — пустой язык и в качестве Ев — произвольный бесконечный НС-язык. В противном случае, — если существует бесконечный НС-язык Е, принадлежа[ций Ы, — применяем ту же лемму при Е, = Е(Р), Е, = Е, Ев — — )о, где р — такое натуральное число, что ни один из языков Е("), где и ) р, в 2' не входит.
Доказанная теорема позволяет легко убедиться в не- распознаваемости ряда более конкретных типов свойств. Имеют место, в частности, такие факты; Сл ед с та не 1. В следующих случаях свойство, нетривиальное в классе НС-язь(кое, нераспознаеаемо е классе НС-грамматик: а) если им обладает лишь конечноечислоНС-языкое; б) если им обладают все конечные языки, соответственно есе языки с конечными дополнениями, кроме, быть может, конечного их числа; 2еа неРАВРешимые АлГОРитмические пРОБлемы [Гл. з 4 вз! ИНВАРИАНТНЫВ СВОИСТВА НС-ГРАММАТИК 267 в) если им обладают толька Б-язв[ки и, быть может, конечное число НС-язь[кое, не являющихся Б-языками, Пункт а) вытекает из того, что число пучков НС-' языков бесконечно, пункт б) — из того, что конечные языки, равно как и языки с конечными дополнениями, образуют пучок (и из нераспознаваемости отрицания нераспознаваемого свойства), пункт в) — из того, что всякий пучок, содержащий Б-язык, целиком состоит из Б-языков (в силу теорем 4.8 и 5.5).
В частности, нераспознаваемы в классе НС-грамма- . тик следующие свойства языков: быть пустым, иметь пустое дополнение, быть конечным, иметь конечное до- полнение, быть бесконтекстным, иметь бесконтекстное ' дополнение, быть автоматным, линейным, метилиней- ным и т.
и. Следствие 2. Какова бы ни была НС-грамматика Го, не существует алгоритма, позволяющего для любой ' НС-грамматики распознать, эквивалентна ли она грал[- . матике Го. Тем более не существует алгоритма для ре- шения общей проблемы эквивалентности НС-грамматик.
Действительно, свойство языка совпадать с Ь(Го) нераспознаваемо по пункту а) следствия 1. С ледствие 3. Если Ео — произвольный бесконеч- ный язык, та не существует алгоритмов, позволяющих по произвольной НС-грамматике Г распознать: -а) содержит ли Е(Г) язык Ео, б) является ли пересечение Ео()Е(Г) пустым. Это вытекает из пункта б) следствия 1, так как свой- ством не содержать Ьо обладают все конечные языки, а свойством иметь с ьо непустое пересечение — все язы- ки с конечными дополнениями. Аналогично получаем Следствие 4. Если Ео — произвольный язык с бес- конечным дополнением, то не существует алгоритмов, позволяющих по произвольной НС-грамматике Г рас- познать: а) содержится ли 1.(Г) в 1.о, б) имеет ли объединение 1.о()1.(Г) пустое дополне- ние.
Из следствия 3 вытекает, например, нераспознавае- мость свойства содержать цепочку, содержащую вхожде- рие )(анной пепочки (соотвстственно начинающуюся или оканчивающуюся вхождением данной цепочки) (ср. упражнение 4.7), из следствия 4 (в случае словаря не менее чем из двух символов) — нераспознаваемость свойства состоять только из цепочек, содержащих вхождение данной цепочки (соответственно начинающихся или оканчивающихся вхождением данной цепочки).
Другие примеры применения теоремы 8.3 см. в упражнениях 8.5 и 8.6. 3 а м е ч а н и е. Если язык Е, конечен, то указанные в следствии 3 алгоритмы существуют, так как соответствующие свойства являются в этом случае булевыми. Аналогично для следствия 4. Итак, мы убедились, что «естественно возникающие» не булевы свойства НС-языков оказываются, как правило, нераспознаваемыми. Возникает вопрос: быть может, распознаваемые свойства исчерпываются булевымиу Следующий пример показывает, что это не так. П р им ер «). Фиксируем (произвольный) словарь Р и сопоставим цепочкам в этом словаре натуральные числа способом, описанным в упражнении 1.3; цепочку, которой сопоставлено число и, будем обозначать ып. Пусть, далее, )à — произвольный рекурсивный язык в словаре )Г, не являющийся НС-языком **). Определим класс языков 2' следующим образом: 1.е 2' =Зп [ып еи(Š— )х) б[(в1! < п)(ы[ яй = ы[ еи 1()].
Свойство языка принадлежать 2' распознаваемо в классе НС (и НСР). В самом деле, для произвольной НС-грамматики Г в силу выбора )т имеем а(Г) чь )[1; поэтому, проверяя последовательно для каждой цепочки ы!, о!2, ..., принадлежит ли она Ь(Г) и принадлежит ли она )т, мы дойдем в конце концов до такой цепочки оп, которая принадлежит либо Е(Г) — )[[, либо )х— — 1.(Г). Если первая из таких цепочек принадлежит 5(Г) — )т, имеем Е(Г)еи .кх, если же она принадлежит Й вЂ” Е(Г), то 1.(Г) Ф 2'.
Вместе с тем свойство принадлежать 2' не булево. Действительно, если Фо Фе(хь ..., хв) — булево ") Указан М. И. Белецким. е») Поимер такого языки при р(У) ) 2 Лостзвляется хотя бы теоремой 2.4, если положись в ией с' = З 1(л) = и. При р(У) = ) нужно еще произвести переколировение, кзк ив стр. 2йа.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
