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

не изменится. В полтченппя К „ о € V ' . грамматике правила вида * - / ? , где ' . вычеркнем и каждому .правилу группы .содержащему вхождения К , допишем ряд п р а в и в которых все­ возможные сочетания вхождений К о * * идений К заменяется вхождениями R , Например, А~*В А -+А А Г „ * заменяется на А—•■ВАС А —►Лес А — -ВВС , очевидно, полученная грамматика удовлетворяет нашим требованиям. Так как выполняется лемма 3, то в дальнейшем будем рассматри- вать АС - грамматики указанного типа и будем обозначать а с - грамматиками. ЛЕИИЛ 4 , Пусть следующим требованиям; I ) Каждое CLCV входит только в одно правило ( 3 ) j £ КС - грамматика Г удовлетворяет являются край- входят только в 2 ) $п и 1щ , где = //,. . . . *• ’*( ними только в данном В 3 3 У У 1 =Уи . . . У , 1 , где V,, и У,*, данное У и только на крайних местах; тогда 2 (С ) - конечнахарактеризуемый и 6 * ( Ш ) - ¡ в г } п ‘ и ( В ) ‘ { ( П 1 . г . ) } . ДОКАЗАТЕЛЬСТВО. Пусть Г ' - это Г без правил (3 ) . . Пусть 2 ^ ¿ ( Г ' ) и г -Х,ТвХ1 * тшгда Х,ТХг ¿ ¿ ( Г ) , г д е Тс —- Т - правило ( 2 ) . Пусть Х , Т Х к Ъ ¿ ( Г " ) , тогда из условий I ) и 2 ) следу­ е т , что Х,ТХк могла быть получена только из Х,Т,Хк г где Те- * Т правило. Таким образом, { ( Х , 7У) . являют­ ся конфигурациями первого ранга языка / ('Г )