Теорема Кука — результат теории автоматов, демонстрирующий, что выполнение двустороннего детерминированного автомата с магазинной памятью может быть смоделировано за линейное время на машине с произвольным доступом к памяти. Открыта в 1970 году учёным из торонтского университета Стивеном Куком. Теорема послужила теоретическим фундаментом для множества линейных алгоритмов обработки текста, таких как алгоритм Манакера, алгоритм Кнута — Морриса — Пратта и алгоритм Вайнера.
Постановка
Детерминированный двусторонний автомат с магазинной памятью может быть определён как набор P = ( Q , Σ , Π , δ , s 0 , Z 0 , s t ) {displaystyle P=(Q,Sigma ,Pi ,delta ,s_{0},Z_{0},s_{t})} , где
- Q {displaystyle Q} — множество состояний автомата,
- Σ {displaystyle Sigma } — входной алфавит,
- Π {displaystyle Pi } — стековый алфавит,
- δ {displaystyle delta } — множество переходов автомата,
- q 0 ∈ Q {displaystyle q_{0}in Q} — начальное состояние автомата,
- Z {displaystyle Z} — нижний символ стека,
- s t {displaystyle s_{t}} — финальное состояние.