Теорема Кука о двусторонних автоматах (Mykjybg Trtg k ;frvmkjkuun] gfmkbgmg])

Перейти к навигации Перейти к поиску

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

Постановка

[править | править код]

Детерминированный двусторонний автомат с магазинной памятью может быть определён как набор , где[1]

  •  — множество состояний автомата,
  •  — входной алфавит,
  •  — стековый алфавит,
  •  — множество переходов автомата,
  •  — начальное состояние автомата,
  •  — нижний символ стека,
  •  — финальное состояние.

Примечания

[править | править код]

Литература

[править | править код]