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

) Пусть найдется простая конфигурация I С , отличная от- 71 о результирующим еловой АСУ, Пусть В - В, А /, ( Г ') 1 тогда « , К в 4 должна принадлежать А (Г') но так как применением правил (2 ) не получишь В, и то надо начинать с В , тогда X => 7 } и К - не простая. - Пусть ¿ € 7 ; и 2 , Х 1А Х 12 ^ А ( Г ' ) > Х ,А Х 2 7} тогда г , Х , К Х ^ %е х ( г ' ) . Но X , и Х А - можно получить только вставкой 7у , но тогда К - должно ^ . Таким образом^ ¡ ( Т н Т ^ ' Г ! ( ¿ ( Г ) ) и [ в ] - ь ( 1 ( г : ) ) . Тогда в силу условия ( I ) и леммы (4 ) из [ I ] ¿ ( Г ) - конечно характеризуемый и Б * ( 1 (Г)) = { В ) и П * {1 (Г ))= {(Т с1 >7 ] ) ) Пример показывает , что в построенный класс входят языки неудовлетворяющие теореме 4 из работы [ I ] У * { а . , * } ¿ = / 6, сУ>а) а '& а 1, . . . , й / 7 д > . . . у Б ( 1 ) = 6 П (Ь ) ^ {Ь, о А ъ ) Но язык этот нельзя породить никакой автоматной грамматикой. Тем не менее: 7 = Пр ] $ : п ; - А ' А -+ВАВ А — 6 . В —*а. . Л1ТГЕРЛТУРА I . А. В.Гладкий. Конфигурационные характеристикн языков. "Проблемы кибернетики", вып. 10 , 2. П.С. Ландвебер. Проблемы разрешения в грамматиках непосредст­ венно составлявших. "Кибернетический сборник", Новая серия, вып. 5 , I