04.01.2023

Теорема Кука — результат теории автоматов, демонстрирующий, что выполнение двустороннего детерминированного автомата с магазинной памятью может быть смоделировано за линейное время на машине с произвольным доступом к памяти. Открыта в 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}} — финальное состояние.

Имя:*
E-Mail:
Комментарий: