Ученые записки математических кафедр вып. 1970 г.

- » и - ЛЕММА 1« Язык V * состоящий из всех фраз в данном словаре V *, конечно характеризуемый. ДОКАЗАТЕЛЬСТВО. Очевидно, если € V * 1 ю ^ Д у а.* 2 г€ V -; и если 2 / Луй< 2 г € V * •, то У * так как V" * состоит из всех фраз в данном словаре о.л^ , Отсюда П (V*) ={(&; , Ду где л £ , Л у , а х б У и Б ( У * ) = У . ТЕОРЕМА 4. Не существует алгоритма, который для любой /(С - грамматики Г отвечал бы на вопрос: принадлежит ли пара ( Я - , У ) множеству простых конфигураций ¿ . ( С ) . Для доказательства нам потребуются два факта: 1 ) Алгоритмически неразрешим вопрос: состоит ли язык, порож­ даемый данной КС - грамматикой, из всех фраз в словаре V ( I ( П = у * ) (СИ. 2 ) . 2 ) Если Ь и ч ) - Б ( 1 г) и П ( 1 4) 1 П ( 1 г ) - ; т о /« у 2 ^ г "(см . I ) . Перейден к доказательству теоремы. Если бы? такой алго­ ритм существовал, то можно было бы проверить П (¿) 5 П (V ) , так как П ( V •) - конечное множество эффективно заданное (лемма I ) . К тому же В Ц ) 2 {«-у, ,.. ; а л | = V -а л г о р и т ­ мически разрешим. Тогда .была бы разрешима проблема I , что приво­ дит к противоречию, следовательно, искомый алгоритм не сущест­ вует . ТЕОРЕМА 5. Нет алгоритма для нахождения Б , ( Ь ) , П Р ( 1 ) где р >, 1 ~ КС - язык. Для доказательства нам потребуются два ф>акта. ' ¿, (С ) ^ ¿ - (К ъ ) - алгоритмически неразрешимо для любых двух К С - грамматик Г4 и . 0 ЛЕММА 2. Если Вр ( ¿ 4) ~ Ьр (В г ) и Пр ( ¿ ,) ~Пр (^г) I , ТО 2 / ^ ~ В £ I »