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

-*5г- ДОКАЗАТЕЛЬСГВО. I . Пусть ¿СЮ ~ * и -X , тогда Х е 6 р { Х < ) = > Х * Б Р (1г) 2. Пусть для фраз длины ¿П - доказано. 3. 8 0 ( ) = П + 1 а ) если X не содержит конфигураций ранга р - рассуждения аналогично базису; б ) пусть X € ¿,1 [ содержит вхождение конфигурации ранга р , тогда найдется простая конфигурация У наименьшего ранга вхо­ дящая в X , X =Х , У Х а , ранг У </> , тогда X , Ч X,, € где Сс - результирующее слово для У По (а,У)^ Пр(1г) так как любая простая конфигурация ранга С < 2 • ’ является простой конфигурацией ранга р , 1 ( Х , а Х , ) < п . и по допущению Х 1 а, Х г €. тогда Х <У Х ^ € / ^ г . Лемма доказана. Доказательство теоремы очевидно. ‘ Построим пример класса нонечнс^характеризуемых КС - языков. ЛЕММА 3 . Для любой КС - грамматики можно Построить V - эквивалентную грамматику Г ' удовлетворяющую следующим требованиям: правила грамматики. Г ‘ разбиваются на 3 группы правил ' Г '= < V / V / Пр в> , где $ с _ фразы над У ' гДе V, » У - фраза над у ' • где / 1 ; Ц и д.■е V ' . ДОКАЗАТЕЛЬСТВО. Если в некоторое правило грамматики X 7 входят слова из I 7 и К ; то все вхождения слов из У заменим на слова Х г , не входящие в У У У , ,и в грамматику Г допи- ием правила Х 1 —*■ й ; . Очевидно, от эт о го язык / ( Г ) ( I ) Пр — 5 с ( 2 ) Ъ — Те (3 ) А — Лс !