Теорема Кука о двусторонних автоматах
Перейти к навигации
Перейти к поиску
Теорема Кука — результат теории автоматов, демонстрирующий, что выполнение двустороннего детерминированного автомата с магазинной памятью может быть смоделировано за линейное время на машине с произвольным доступом к памяти. Открыта в 1970 году учёным из торонтского университета Стивеном Куком. Теорема послужила теоретическим фундаментом для множества линейных алгоритмов обработки текста, таких как алгоритм Манакера, алгоритм Кнута — Морриса — Пратта и алгоритм Вайнера.
Постановка
Детерминированный двусторонний автомат с магазинной памятью может быть определён как набор , где[1]
- — множество состояний автомата,
- — входной алфавит,
- — стековый алфавит,
- — множество переходов автомата,
- — начальное состояние автомата,
- — нижний символ стека,
- — финальное состояние.