Однозначный конечный автомат

В теории автоматов однозначный конечный автомат ( UFA ) — это недетерминированный конечный автомат (NFA) такой, что каждое слово имеет не более одного принимающего пути. Каждый детерминированный конечный автомат (DFA) является UFA, но не наоборот. DFA, UFA и NFA признают один и тот же класс формальных языков . С одной стороны, NFA может быть экспоненциально меньшим, чем эквивалентный DFA. С другой стороны, некоторые проблемы легко решаются на DFA, а не на UFA. Например, для данного автомата A автомат A ′ , который принимает дополнение к A, может быть вычислен за линейное время, когда A является DFA, тогда как известно, что это невозможно сделать за полиномиальное время для UFA. Следовательно, UFA представляют собой смесь миров DFA и NFA; в некоторых случаях они приводят к меньшим автоматам, чем DFA, и более быстрым алгоритмам, чем NFA.

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

NFA кортежем из представлен пяти формально $A=(Q,\Sigma ,\Delta ,q_{0},F)$. UFA слова — это NFA, такой, что для каждого $w=a_{1}a_{2}...a_{n}$, существует не более одной последовательности состояний $r_{0},r_{1},...,r_{n}$, в $Q$ со следующими условиями:

1. $r_{0}=q_{0}$;
2. $r_{i+1}\in \Delta (r_{i},a_{i+1})$ для $i=0,...n-1$;
3. $r_{n}\in F$.

На словах эти условия гласят, что, если $w$ принимается $A$, существует ровно один принимающий путь, то есть один путь от начального состояния к конечному состоянию, который помечен знаком $w$.

Пример

Позволять $L$ — набор слов в алфавите { a , b } я последняя буква которого , n- — $a$. На рисунках показаны DFA и UFA, принимающие этот язык для n=2 .

Детерминированный автомат (ДКА) для языка L при n=2

Однозначный конечный автомат (УКА) для языка L при n=2

Минимальный прием DFA $L$ имеет 2 ^н утверждает, по одному для каждого подмножества {1... n }. Есть УФА $n+1$ государства, которые принимают $L$: он угадывает n -ю последнюю букву, а затем проверяет, что только $n-1$ буквы остались. Это действительно однозначно, поскольку существует только одна n- я последняя буква.

Инклюзивность, универсальность, эквивалентность

Три PSPACE -трудные задачи для общего NFA относятся к PTIME для DFA и сейчас рассматриваются.

Включение

За полиномиальное время можно решить, является ли язык UFA подмножеством другого языка UFA.

показывать Эскиз доказательства включения

Let A and B be two UFAs. Let L(A) and L(B) be the languages accepted by those automata. Then L(A)⊆L(B) if and only if L(A∩B)=L(A), where A∩B denotes the Cartesian product automaton, which can be proven to be also unambiguous. Now, L(A∩B) is a subset of L(A) by construction; hence both sets are equal if and only if for each length n∈$\mathbb {N}$, the number of words of length n in L(A∩B) is equal to the number of words of length n in L(A). It can be proved that is sufficient to check each n up to the product of the number of states of A and B. The number of words of length n accepted by an automaton can be computed in polynomial time using dynamic programming, which ends the proof.

Универсальность, эквивалентность

Проблема универсальности и эквивалентности, также принадлежат PTIME за счет сведения к проблеме включения.

Проверка однозначности автомата

Для недетерминированного конечного автомата $A$ с $n$ государства и $m$ буквенный алфавит, разрешимый во времени $O(n^{2}m)$ ли $A$ является однозначным.

показывать Эскиз доказательства однозначности
It suffices to use a fixpoint algorithm to compute the set of pairs of states q and q' such that there exists a word w which leads both to q and to q' . The automaton is unambiguous if and only if there is no such a pair such that both states are accepting. There are Θ(n2) state pairs, and for each pair there are m letters to consider to resume the fixpoint algorithm, hence the computation time.

Некоторые свойства

• Учитывая UFA A и целое число n , можно за полиномиальное время подсчитать количество слов размера n, принимаются A. которые помощью простого алгоритма динамического программирования: для каждого состояния q A и Это можно сделать с $i\in \{0,\ldots ,n\}$, вычислите количество слов размера ni, имеющих серию, начинающуюся с q и заканчивающуюся конечным состоянием. Напротив, та же проблема #P-трудна для NFA.
• Декартово произведение (пересечение) двух УФА является УФА.
• Понятие однозначности распространяется на преобразователи конечных состояний и взвешенные автоматы . Если преобразователь конечных состояний T однозначен, то каждое входное слово связано T не более чем с одним выходным словом. Если весовой автомат A однозначен, то множество весов не обязательно должно быть полукольцом , вместо этого достаточно рассмотреть моноид . Действительно, существует не более одного принимающего пути.

Государственная сложность

Основная статья: Государственная сложность

Математические доказательства того, что каждому УФА для языка необходимо определенное количество состояний, были впервые предложены Шмидтом. Люнг доказал, что ДКА, эквивалентный $n$-государство УФА требует $2^{n}$ утверждается в худшем случае, и что UFA эквивалентен конечно неоднозначному $n$-государственная НФА требует $2^{n}-1$ государства в худшем случае.

Йирасек, Йираскова и Шебей исследовал состояние сложности основных регулярных операций на языках, представленных УФА. Они, в частности, доказали, что для каждого $n$-государство УФА, где $n\geq 7$, то дополнение к языку, которое он принимает, принимается УФА не более чем с $2^{0.79n+\log n}$ государства. Этот результат позже был улучшен Инджев и Кифер. максимум ${\sqrt {n+1}}\cdot 2^{0.5n}$ государства для всех $n\geq 0$.

Раскин показал, что UFA не могут быть дополнены за полиномиальное время, даже в NFA: он показывает, что в худшем случае дополнение UFA n состояниями в NFA требует суперполиномиального числа состояний. Эта нижняя оценка позже была улучшена Гёосом, Кифером и Юанем.

Для однобуквенного алфавита Охотин доказал, что ДКА, эквивалентный $n$-государство УФА требует $\exp \left(\Theta \left({\sqrt[{3}]{n(\ln n)^{2}}}\right)\right)$ государства в худшем случае.

Ссылки

• Кристоф Лёдинг, Однозначные конечные автоматы , Развитие теории языка , (2013), стр. 29–30 ( Слайды )