Unambiguous finite automaton

In automata theory, an unambiguous finite automaton (UFA) is a special kind of a nondeterministic finite automaton (NFA). 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, it is not known whether it can be done in polynomial time for UFA. 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.

An NFA is represented formally by a 5-tuple, A=(Q, Σ, Δ, q₀, F). An UFA is an NFA such that, for each word w = a₁a₂ … a_n, there exists at most one sequence of states r₀,r₁, …, r_n, in Q with the following conditions:

In words, those conditions state that, if w is accepted by A, there is exactly one accepting path, that is, one path from an initial state to a final state, labelled by w.

Let L be the set of words over the alphabet {a,b} whose nth last letter is an a. The figures show a DFA and a UFA accepting this language for n=2.

The minimal DFA accepting L has 2ⁿ states, one for each subset of {1...n}. There is an UFA of n+1 states which accepts L: it guesses the nth last letter, and then verifies that only n-1 letters remain. It is indeed unambiguous as there exists only one nth last letter.

Three PSPACE-hard problems for general NFA belong to PTIME for DFA and are now considered.

It is decidable in polynomial-time whether an automaton's language is a subset of an automaton of another language.

Let A and B be two automata. 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 set are equal if and only if for each length 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.

...
Wikipedia