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

-353- а . г . мшкис О КОНЕЧНО ХАРАКТЕРИЗУЕМЫХ ЯЗЫКАХ '■ Введение В заметке рассматривается вопрос о существовании языка с данное конфигурационной характеристикой. Доказывается конечная характеризуемость одного класса КС-языков, алгоритмическая нераз­ решимость вопроса о нахождении конфигурационной характеристики * КС-языков. Все использованные определения можно найти в указанной литера­ туре. Все языки рассматривается над допустимыми словарями. Дадим определение простой конфигурации; Конфигурация называется простой^если она не содержит вхожде­ ний конфигураций отличных от себя самой / » т о определение отличает­ ся от определения данного в работе I / . Рассмотрим вопрос-о том, может ли любая пара Б Г(Х,,... ,Х„.}, где X, ¡ Х 1 , . . . , X V - фразы над V ,и П ~ {(&с , У )} , где &<; € V и. Ус фразы над V быть выбрана в качестве приведенной конфигурационной характеристики некоторого языка X ? ТЕОРЕМА I . Если Б - ] - конечное множество фраз над некоторым словарем У , то всегда можно построить такой язык Z над ]/ , для которого (Х,,х ............Х » ) г 6 ( А ) . ДОКАЗАТЕЛЬСТВО. Пусть X, ,Хг , . . . , Х „, - фразы над 8 ^ . Возьмем вспомогательный словарь I/ Пр . Построим КС -грамматику [Г -X У;У , ; П р ^ > *, у которой правила разбиты на три группы: I. Пр — -Хс где X Б и X ; получено заменой букв ^ на й ; ;