In automata theory, an unambiguous finite automaton (UFA) is a nondeterministic finite automaton (NFA) such that each word has at most one accepting path. Each deterministic finite automaton (DFA) is an UFA, but not vice versa. DFA, UFA, and NFA recognize exactly the same class of formal languages. On the one hand, an NFA can be exponentially smaller than an equivalent DFA. On the other hand, some problems are easily solved on DFAs and not on UFAs. For example, given an automaton A, an automaton A′ which accepts the complement of A can be computed in linear time when A is a DFA, whereas it is known that this cannot be done in polynomial time for UFAs. Hence UFAs are a mix of the worlds of DFA and of NFA; in some cases, they lead to smaller automata than DFA and quicker algorithms than NFA.
Formal definition An NFA is represented formally by a 5-tuple, A = ( Q , Σ , Δ , q 0 , F ) {\displaystyle A=(Q,\Sigma ,\Delta ,q_{0},F)} . An UFA is an NFA such that, for each word w = a 1 a 2 . . . a n {\displaystyle w=a_{1}a_{2}...a_{n}} , there exists at most one sequence of states r 0 , r 1 , . . . , r n {\displaystyle r_{0},r_{1},...,r_{n}} , in Q {\displaystyle Q} with the following conditions:
r 0 = q 0 {\displaystyle r_{0}=q_{0}} ;
r i + 1 ∈ Δ ( r i , a i + 1 ) {\displaystyle r_{i+1}\in \Delta (r_{i},a_{i+1})} for i = 0 , . . . n − 1 {\displaystyle i=0,...n-1} ;
r n ∈ F {\displaystyle r_{n}\in F} . In words, those conditions state that, if w {\displaystyle w} is accepted by A {\displaystyle A} , there is exactly one accepting path, that is, one path from an initial state to a final state that is labelled by w {\displaystyle w} .
Example Let L {\displaystyle L} be the set of words over the alphabet {a,b} whose nth last letter is an a {\displaystyle a} . The figures show a DFA and a UFA accepting this language for n=2.
The minimal DFA accepting L {\displaystyle L} has 2n states, one for each subset of {1...n}. There is an UFA of n + 1 {\displaystyle n+1} states which accepts L {\displaystyle L} : it guesses the nth last letter, and then verifies that only n − 1 {\displaystyle n-1} letters remain. It is indeed unambiguous as there exists only one nth last letter.
Inclusion, universality, equivalence Three PSPACE-hard problems for general NFA belong to PTIME for DFA and are now considered.
Inclusion It is decidable in polynomial-time whether an UFA's language is a subset of another UFA's language.
Universality, equivalence The problem of universality and of equivalence, also belong to PTIME, by reduction to the inclusion problem.
Checking whether an automaton is unambiguous For a nondeterministic finite automaton A {\displaystyle A} with n {\displaystyle n} states and an m {\displaystyle m} letter alphabet, it is decidable in time O ( n 2 m ) {\displaystyle O(n^{2}m)} whether A {\displaystyle A} is unambiguous.
Some properties Given a UFA A and an integer n, one can count in polynomial time the number of words of size n that are accepted by A. This can be done by a simple dynamic programming algorithm: for every state q of A and i ∈ { 0 , … , n } {\displaystyle i\in \{0,\ldots ,n\}} , compute the number of words of size n-i having a run starting at q and ending in a final state. By contrast, the same problem is #P-hard for NFAs, but it admits an FPRAS. The cartesian product (intersection) of two UFAs is a UFA. The notion of unambiguity extends to finite state transducers and weighted automata. If a finite state transducer T is unambiguous, then each input word is associated by T to at most one output word. If a weighted automaton A is unambiguous, then the set of weight does not need to be a semiring, instead it suffices to consider a monoid. Indeed, there is at most one accepting path. Minimizing UFA is NP-complete. More precisely, given a UFA A, deciding if there is an equivalent UFA with less than k states is NP-complete. The bound also holds when the input is given as a DFA instead.
State complexity
… excerpt ends here. Continue reading the full article.
