RUS  ENG
Полная версия
ЖУРНАЛЫ // Математические заметки // Архив

Матем. заметки, 1991, том 50, выпуск 1, страницы 34–40 (Mi mzm3000)

Не существует перечислимого семейства контекстно-свободных грамматик, порождающего класс всех однозначных языков

К. Ю. Горбунов

Московский государственный университет им. М. В. Ломоносова

Аннотация: Доказано утверждение заглавия и попутно построен класс языков такой, что для контекстно-свободных грамматик, задающих языки этого класса, разрешима проблема эквивалентности с произвольной контекстно-свободной грамматикой.
Библиогр. 9 назв.

УДК: 519.765

Поступило: 04.04.1988
Исправленный вариант: 10.11.1989


 Англоязычная версия: Mathematical Notes, 1991, 50:1, 683–690

Реферативные базы данных:


© МИАН, 2024