Аннотация:
Всякий контекстно-свободный язык можно задать некоторой грамматикой, основанной на исчислении Ламбека. Так называемые конъюнктивные грамматики являются обобщением контекстно-свободных грамматик: в них в правой части подстановок разрешается употреблять не только слова, но и конъюнкции слов.
В докладе рассматриваются языки, порождаемые конъюнктивной грамматикой с условием, что правая часть каждой подстановки начинается с терминального символа. Всякий контекстно-свободный язык можно
задать контекстно-свободной грамматикой в такой форме. Вопрос о возможности задания произвольной конъюнктивной грамматики в такой форме остается открытым. Доказано, что каждая конъюнктивная грамматика в указанной форме порождает язык, задаваемый также грамматикой, основанной на исчислении Ламбека, расширенном добавлением операции пересечения языков.
|
