Двусторонний конечный автомат - Two-way finite automaton

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

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

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

2DFA были представлены в основополагающей статье 1959 г. Рабин и Скотт,^[1] кто доказал, что их мощность эквивалентна одностороннему DFA. То есть любой формальный язык который может быть распознан с помощью 2DFA, может быть распознан с помощью DFA, который только исследует и использует каждый символ по порядку. Поскольку DFA, очевидно, являются частным случаем 2DFA, это означает, что оба типа машин точно распознают класс обычные языки. Однако эквивалентный DFA для 2DFA может потребовать экспоненциально много состояний, что делает 2DFA гораздо более практичным представлением алгоритмов для некоторых общих проблем.

2DFA также эквивалентны машины Тьюринга только для чтения которые используют только постоянный объем места на своей рабочей ленте, поскольку любой постоянный объем информации может быть включен в состояние конечного управления через конструкцию продукта (состояние для каждой комбинации состояния рабочей ленты и состояния управления).

Формальное описание

Формально двусторонний детерминированный конечный автомат можно описать следующими 8-кортеж: ${displaystyle M = (Q, Sigma, L, R, delta, s, t, r)}$ куда

• ${displaystyle Q}$ - конечное непустое множество состояния
• ${displaystyle Sigma}$ конечный непустой набор входного алфавита
• ${displaystyle L}$ это левый указатель конца
• ${displaystyle R}$ это правый конец
• ${displaystyle delta: Q imes (Sigma cup {L, R}) ightarrow Q imes {mathrm {left, right}}}$
• ${displaystyle s}$ это начальное состояние
• ${displaystyle t}$ это конечное состояние
• ${displaystyle r}$ это состояние отказа

Кроме того, должны быть выполнены следующие два условия:

• Для всех ${displaystyle qin Q}$

${displaystyle delta (q, L) = (q ^ {prime}, mathrm {right})}$ для некоторых ${displaystyle q ^ {prime} in Q}$

${displaystyle delta (q, R) = (q ^ {prime}, mathrm {left})}$ для некоторых ${displaystyle q ^ {prime} in Q}$

Он говорит, что должен быть возможен какой-то переход, когда указатель на алфавите достигает конца.

• Для всех символов ${displaystyle sigma in Sigma cup {L}}$

${displaystyle delta (t, sigma) = (t, R)}$

${displaystyle delta (r, sigma) = (r, R)}$

${displaystyle delta (t, R) = (t, L)}$

${displaystyle delta (r, R) = (r, L)}$

В нем говорится, что как только автомат достигает состояния принятия или отклонения, он остается там навсегда, а указатель переходит к крайнему правому символу и бесконечно циклически перемещается там.^[2]

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

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

• ${displaystyle delta: Q imes (чашка сигмы {L, R}) ightarrow 2 ^ {Q imes {mathrm {left, right}}}}$.

Как стандартный односторонний NFA, 2NFA принимает строку, если принимает хотя бы одно из возможных вычислений. Как и 2DFA, 2NFA также принимают только обычные языки.

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

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

• ${displaystyle Q = Q_ {exists} чашка Q_ {forall}}$ куда ${displaystyle Q_ {exists} cap Q_ {forall} = emptyset}$.

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

Компромиссы сложности состояния

Двусторонние и односторонние конечные автоматы, детерминированные, недетерминированные и чередующиеся, принимают один и тот же класс регулярных языков. Однако преобразование автомата одного типа в эквивалентный автомат другого типа приводит к увеличению числа состояний. Капуцис^[3] определил, что преобразование ${displaystyle n}$-state 2DFA для эквивалентного DFA требует ${displaystyle n (n ^ {n} - (n-1) ^ {n})}$ состояния в худшем случае. Если ${displaystyle n}$-состояние 2DFA или 2NFA преобразуется в NFA, наихудшее количество требуемых состояний ${displaystyle {inom {2n} {n + 1}} = Oleft ({frac {4 ^ {n}} {sqrt {n}}} ight)}$. Ladner, Lipton и Stockmeyer.^[4]доказал, что ${displaystyle n}$-состояние 2AFA может быть преобразовано в DFA с помощью ${displaystyle 2 ^ {n2 ^ {n}}}$ Для преобразования 2AFA в NFA требуется ${displaystyle 2 ^ {Theta (nlog n)}}$ состояния в худшем случае, см. Гефферт и Охотин.^[5]

Нерешенная проблема в информатике: Каждый ${displaystyle n}$-состояние 2NFA имеет эквивалент ${displaystyle operatorname {poly} (n)}$-состояние 2DFA? (больше нерешенных проблем в информатике)

Вопрос о том, можно ли каждую 2NFA преобразовать в 2DFA с полиномиальным увеличением числа состояний, остается открытым. Проблема была поднята Сакодой и Sipser,^[6]кто сравнил это с P против NP проблема в теория сложности вычислений.Berman и лингамы^[7] обнаружил формальную связь между этой проблемой и L против. NL открытая проблема, см. Капуцис^[8] для точного отношения.

Подметальные автоматы

Подметающие автоматы - это 2DFA особого типа, которые обрабатывают входную строку, чередуя развертки слева направо и справа налево, поворачиваясь только на концевых маркерах. Sipser^[9] построил последовательность языков, каждый из которых принимается NFA с n состояниями, но не принимается никакими подметающими автоматами с числом менее ${displaystyle 2 ^ {n}}$ состояния.

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

В 1997 году концепция 2DFA была обобщена на квантовые вычисления к Джон Уотроус «О силе двухсторонних квантовых автоматов с конечным числом состояний», в которой он демонстрирует, что эти машины могут распознавать нерегулярные языки и поэтому являются более мощными, чем DFA.^[10]

Двусторонний выталкивающий автомат

А выталкивающий автомат которому разрешено двигаться в любом направлении на входной ленте, называется двухсторонний автомат (2PDA);^[11] он был изучен Хартманисом, Льюисом и Стернсом (1965).^[12]Ахо, Хопкрофт, Ульман (1968)^[13]и повар (1971)^[14] охарактеризовал класс языков, распознаваемых детерминированными (2DPDA) и недетерминированный (2NPDA) двусторонние выталкивающие автоматы; Грей, Харрисон и Ибарра (1967) исследовали закрывающие свойства этих языков. ^[15]

Рекомендации