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

2 . — а с ■ з; а- — а £ где - /п<г<с е Ш ; л ( Г ) Рассмотрим конфигурационную характеристику языка Докажем, что Я (X, -Б - [X, ,Х» .... ,Х„.], Действительно, пусть пара (У ,й -^ € П (¿*) , тогда языку I (Г) должна принадлежать фраза вида 2 , У ^ г . Следовательно, У может быть только вида Л<г ...а ^ С (У ) = ^ * \ Легко видеть, что еслж 2 , 6 X. (А1,) ,! то ж Фраза .Т о г д а Л ( % } г ) ) = { ( ъ га ^ м , ) ] Но X, )Х1_,..,/Х П. не содержат вхождений фраз следовательно,' ( Х , , Х , .......... Х ^ £ ( Л ^ Но так как все остальные фразы* порождаемые грамматикой Г V имеют вид 2 ,, , ю (X, ,Х *,.,.,Хл| ~Б (Х< (Б ) ) , что и требовалось доказать. ТЕОРЕМА 2 . Не для всякого произвольно внбраяного множества пар {(& ; , У { ) ] = ^ судествует язык X. для которого }(а{,Ус)}--П(А) ДОКАЗАТЕЛЬСТВО. Пусть П -{(а 1<Х^)'1[$1Щ = П ( Б ) . Если искомый язык X. содержит фразу вида Х1й Х к \ тогда X , с и X* € Ь , х ¿ Х г€ •; так как других простых конфигура­ ций нет, то эти замены возможны по определению простой конфигура­ ции. Аналогично Ь Х ^ Б ^ Х ,а -Х ь £ Б . Таким образом, & и ^ должны быть взаимозамещаемы в языке /у . Тогда (Л, Щ , (л,ва), (а ,аа ).(в . №), (4, 4а) также являются простыми конфигурациями языка Ь . Мы получили противоречие. Теорема доказана. ТЕОРЕМА 3 . Если судествует язык ¿-ц с данными Б и язык то не всегда найдется язык Б с харак- ,с данныии П