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

Постановка Детерминированный двусторонний автомат с магазинной памятью может быть определён как набор , где  — множество состояний автомата,  — входной алфавит,  — стековый алфавит,  — множество переходов автомата,  — начальное состояние автомата,  — нижний символ стека,  — финальное состояние.

Примечания

Литература

Категория:Теоремы теории автоматов