RUS  ENG
Полная версия
ЖУРНАЛЫ // Проблемы передачи информации // Архив

Пробл. передачи информ., 1979, том 15, выпуск 1, страницы 99–104 (Mi ppi1480)

Теория языков

Об одном классе грамматик с разорванными контекстными условиями применения продукций

Б. Е. Кац


Аннотация: Показывается, что в классе языков типа $EL+NL$, введенном М. В. Ломковской, в некотором смысле представимо пересечение произвольного конечного числа языков этого же типа. Отсюда следует неразрешимость проблем пустоты и конечности языка в классе грамматик типа $EL+NL$ и незамкнутость класса языков типа $EL+NL$ относительно гомоморфизмов.

УДК: 621.391.194

Поступила в редакцию: 31.01.1977


 Англоязычная версия: Problems of Information Transmission, 1979, 15:1, 75–79

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


© МИАН, 2024