Аппаратная конструкция для решения проблемы экспоненциального взрыва для одного класса регулярных языков

Авторы: Бернадотт А., Галатенко А.В.
Журнал: Интеллектуальные системы. Теория и приложения (ранее: Интеллектуальные системы по 2014, № 2, ISSN 2075-9460)
Том: 23
Номер: 4
Год издания: 2019
Издательство: [б.и.]
Местоположение издательства: М.
Первая страница: 27
Последняя страница: 38
Аннотация: Известно, что язык, задаваемый регулярным выражением вида .∗αi.∗βi.∗, где αi, βi — слова над некоторым алфавитом, в общем случае для распознавания конечным детерминированным автоматом требует экспоненциальное по n число состояний. В работе предлагается конструкция структурного автомата, распознающего языки из данного класса и имеющего полиномиальную пространственную сложность. Ключевые слова: ДКА, структурный автомат, регулярный язык, экспоненциальный взрыв.
Добавил в систему: Бернадотт Александра

	ИСТИНА	Войти в систему Регистрация
	ИСТИНА ПсковГУ
	Главная Поиск Статистика О проекте Помощь

ИСТИНА