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

Постановка

Детерминированный двусторонний автомат с магазинной памятью может быть определён как набор ${\displaystyle P=(Q,\Sigma ,\Pi ,\delta ,s_{0},Z_{0},s_{t})}$ , где

• ${\displaystyle Q}$ — множество состояний автомата,
• ${\displaystyle \Sigma }$ — входной алфавит,
• ${\displaystyle \Pi }$ — стековый алфавит,
• ${\displaystyle \delta }$ — множество переходов автомата,
• ${\displaystyle q_{0}\in Q}$ — начальное состояние автомата,
• ${\displaystyle Z}$ — нижний символ стека,
• ${\displaystyle s_{t}}$ — финальное состояние.

Примечания

Литература

• Andersen N., (англ.) // / , J. Hartmanis , — Berlin, Heidelberg, New York City, London: Springer , 1994. — P. 1—18. — ISSN ; —
• Mogensen T. Æ. (англ.) // — Elsevier BV , 1994. — Vol. 52, Iss. 1. — P. 15—22. — ISSN ; —
• — 1985. — С. 341—356. —
• Galil Z., Seiferas J. (англ.) // Journal of the ACM / — New York City: Association for Computing Machinery , 1978. — Vol. 25, Iss. 1. — P. 102—111. — ISSN ; —
• (англ.) // — Elsevier BV , 1977. — Vol. 6, Iss. 4. — P. 110—112. — ISSN ; —
• Manacher G. K. (англ.) // Journal of the ACM / — New York City: Association for Computing Machinery , 1975. — Vol. 22, Iss. 3. — P. 346—351. — ISSN ; —
• , Breslauer D., (англ.) // — Elsevier BV , 1995. — Vol. 141, Iss. 1-2. — P. 163—173. — ISSN ; —
• Aho A. , Hopcroft J. E. , Ullman J. D. (англ.) — Boston: Addison-Wesley , 1974. — 480 p. — ISBN 978-0-201-00029-0
• Knuth D. E. , James H. Morris, Jr. , Pratt V. R. (англ.) // / M. Sudan — , 1977. — Vol. 6, Iss. 2. — P. 323—350. — ISSN ; —