Автомат очереди

Очереди машины или очередь автомат является конечным автоматом с возможностью хранить и извлекать данные из памяти бесконечномерной очереди . Это модель вычислений, эквивалентная машине Тьюринга , и поэтому она может обрабатывать тот же класс формальных языков .

Теория [ править ]

Автомат очередей можно определить как набор из шести элементов.

${\displaystyle M=(Q,\Sigma ,\Gamma ,\$,s,\delta )}$ куда

• ${\displaystyle \,Q}$- конечный набор состояний ;
• ${\displaystyle \,\Sigma \subset \Gamma }$- конечный набор входного алфавита ;
• ${\displaystyle \,\Gamma }$- алфавит конечной очереди ;
• ${\displaystyle \,\$\in \Gamma -\Sigma }$- начальный символ очереди ;
• ${\displaystyle \,s\in Q}$это начальное состояние ;
• ${\displaystyle \,\delta :Q\times \Gamma \rightarrow Q\times \Gamma ^{*}}$- функция перехода .

Конфигурация машины - это упорядоченная пара ее состояния и содержимого очереди , где означает закрытие по Клини . Начальная конфигурация входной строки определяется как , а переход от одной конфигурации к другой определяется как:${\displaystyle \,(q,\gamma )\in Q\times \Gamma ^{*}}$${\displaystyle \,\Gamma ^{*}}$${\displaystyle \,\Gamma }$${\displaystyle \,x}$${\displaystyle \,(s,x\$)}$${\displaystyle \rightarrow _{M}^{1}}$

${\displaystyle \,(p,A\alpha )\rightarrow _{M}^{1}(q,\alpha \gamma )}$

где - символ из алфавита очереди, - последовательность символов очереди ( ), и . Обратите внимание на свойство очереди в отношении «первым пришел - первым обслужен».${\displaystyle A}$${\displaystyle \alpha }$${\displaystyle \alpha \in \Gamma ^{*}}$${\displaystyle (q,\gamma )=\delta (p,A)}$

Машина принимает строку, если после конечного числа переходов начальная конфигурация эволюционирует и исчерпывает строку (достигая нулевой строки ), или ^[1]${\displaystyle \,x\in \Sigma ^{*}}$${\displaystyle \,\epsilon }$${\displaystyle \,(s,x\$)\rightarrow _{M}^{*}(q,\epsilon ).}$

Полнота по Тьюрингу [ править ]

Мы можем доказать, что машина с очередями эквивалентна машине Тьюринга, показав, что машина с очередями может моделировать машину Тьюринга и наоборот.

Машину Тьюринга можно смоделировать с помощью машины очереди, которая постоянно хранит копию содержимого машины Тьюринга в своей очереди, с двумя специальными маркерами: одним для положения головы TM и одним для конца ленты; его переходы имитируют переходы TM, проходя через всю очередь, выталкивая каждый из ее символов и повторно ставя либо вытянутый символ, либо, около позиции заголовка, эквивалент эффекта перехода TM.

Машина очереди может быть смоделирована машиной Тьюринга, но проще - многоленточной машиной Тьюринга , которая, как известно, эквивалентна обычной машине с одной лентой. Имитирующая машина очереди считывает ввод с одной ленты и сохраняет очередь на второй, при этом нажатия и толчки определяются простыми переходами к начальному и конечному символам ленты. ^[2] Формальным доказательством этого часто является упражнение на курсах теоретической информатики.

Приложения [ править ]

Машины очередей предлагают простую модель, на которой можно строить компьютерные архитектуры , ^{[3] [4]} языки программирования или алгоритмы . ^{[5] [6]}

См. Также [ править ]

• Вычислимость
• Эквиваленты машины Тьюринга
• Детерминированный конечный автомат
• Выталкивающий автомат
• Система тегов
• Manufactoria , браузерная флеш-игра, в которой игроку предлагается реализовать различные алгоритмы с использованием модели машины очереди.

Ссылки [ править ]