Введение

Тип конечного автомата в теории автоматов.
В информатике, в частности в теории автоматов, двусторонний конечный автомат — это конечный автомат, которому разрешено повторно считывать входные данные.

Двусторонний детерминированный конечный автомат

Двусторонний детерминированный конечный автомат (2DFA) — это абстрактная машина, являющаяся обобщенной версией детерминированного конечного автомата (DFA), способная повторно просматривать уже обработанные символы. Как и в DFA, существует конечное число состояний с переходами между ними, основанными на текущем символе, но каждый переход также имеет метку, указывающую, сдвинется ли позиция машины во входной последовательности влево, вправо или останется на месте. Эквивалентно, 2DFA можно рассматривать как машину Тьюринга только для чтения без рабочей ленты, имеющую только входную ленту для чтения. 2DFA были введены в основополагающей работе 1959 года Рабином и Скоттом, которые доказали, что они обладают эквивалентной вычислительной мощностью с односторонними DFA. То есть любой формальный язык, распознаваемый 2DFA, может быть распознан DFA, который последовательно просматривает и потребляет каждый символ. Поскольку DFA, очевидно, является частным случаем 2DFA, это подразумевает, что оба типа машин распознают ровно класс регулярных языков. Однако эквивалентный DFA для 2DFA может потребовать экспоненциальное количество состояний, что делает 2DFA гораздо более практичным представлением для алгоритмов решения некоторых распространенных задач. 2DFA также эквивалентны машинам Тьюринга только для чтения, использующим постоянный объем памяти на рабочей ленте, поскольку любой постоянный объем информации может быть закодирован в конечном управляющем состоянии посредством построения по произведению (состояние для каждой комбинации состояния рабочей ленты и управляющего состояния).

Двусторонний недетерминированный конечный автомат

Двусторонний недетерминированный конечный автомат (2NFA) может иметь несколько переходов, определенных для одной и той же конфигурации. Его функция перехода аналогична функции перехода стандартного одностороннего NFA. 2NFA принимает строку, если хотя бы одна из возможных последовательностей вычислений является принимающей. Как и 2DFA, 2NFA распознает только регулярные языки.

Двусторонний чередующийся конечный автомат

Двусторонний чередующийся конечный автомат (2AFA) является двусторонним расширением чередующегося конечного автомата (AFA). Его множество состояний определяется как

где состояния в и называются экзистенциальными и универсальными соответственно. В экзистенциальном состоянии 2AFA недетерминированно выбирает следующее состояние, как и NFA, и принимает, если хотя бы одно из полученных вычислений принимает. В универсальном состоянии 2AFA переходит во все следующие состояния и принимает, если все полученные вычисления принимают.

Компромиссы сложности государства

Двусторонние и односторонние конечные автоматы, детерминированные и недетерминированные и чередующиеся, распознают один и тот же класс регулярных языков. Однако, преобразование автомата одного типа в эквивалентный автомат другого типа приводит к экспоненциальному росту числа состояний. Christos Kapoutsis установил, что преобразование 2DFA с *n* состояниями в эквивалентный DFA требует *n*² состояний в худшем случае. Если 2DFA с *n* состояниями или 2NFA преобразуется в NFA, то наихудшее число необходимых состояний равно Ladner, Lipton и Stockmeyer. Доказали, что 2AFA с *n* состояниями может быть преобразован в DFA с 2ⁿ состояниями. Преобразование 2AFA в NFA требует 2ⁿ состояний в худшем случае, см. Geffert и Okhotin. Остаётся открытым вопрос о том, можно ли любой 2NFA преобразовать в 2DFA лишь с полиномиальным увеличением числа состояний. Этот вопрос был поставлен Sakoda и Sipser, которые сравнили его с проблемой P vs. NP в теории вычислительной сложности. Berman и Lingas обнаружили формальную связь между этой проблемой и открытой проблемой L vs. NL, подробности см. у Kapoutsis.

Автоматы для чистки

Прочищающие автоматы — это 2DFA особого типа, которые обрабатывают входную строку, совершая чередующиеся проходы слева направо и справа налево, поворачивая только на ограничителях. Сипсер построил последовательность языков, каждый из которых принимается NFA с n состояниями, но не принимается ни одним прочищающим автоматом с меньшим числом состояний.

Двусторонний квантовый конечный автомат

Концепция 2DFAs была обобщена для квантовых вычислений в 1997 году Джоном Уотрусом в работе "О мощности двухсторонних квантовых конечных автоматов", где он показал, что эти машины способны распознавать нерегулярные языки и, следовательно, превосходят DFA по мощности.