Скінченні автомати. Теорія, алгоритми, складність. Підручник для студентів ВНЗ. Сергій Лук'янович Кривий. Букрек

У підручнику розглядаються основні поняття теорії скінченних автоматів над словами скінченної та нескінченної довжини. Наводяться алгоритми синтезу, аналізу, еквівалентних перетворень скінченних автоматів, а також приклади розв'язання основних алгоритмічних проблем для мов, акцептованих цими автоматами. Описуються зв'язки теорії скінченних автоматів з темпоральною лінійною логікою та їх застосування в комп'ютерній алгебрі, трансляції, ідентифікації, генетиці, верифікації тощо. Розглянуто основні поняття теорії скінченних часових автоматів та їх застосування до верифікації властивостей систем з часовими обмеженнями і, зокрема, до аналізу властивостей часових мереж Петрі. Описані основні властивості СА над деревами та властивості магазинних автоматів. Підручник призначений для наукових співробітників, аспірантів, викладачів та студентів старших курсів вищих навчальних закладів.