Unambiguous finite automaton

In automata theory, the Unambigous finite automaton (UFA) is a special kind of a nondeterministic finite automaton (NFA). Each deterministic finite automaton (DFA) is an UFA. DFA, UFA and NFA recognizes exactly the same formal languages.

On the one hand, NFA can be exponentially smaller than equivalent DFA. On the other hand, some problems are exponentially quicker on DFA than on UFA. UFAs are a mixed of both world, in some case, it leads to small automata and quicker algorithm.

Formal definition

An NFA is represented formally by a 5-tuple, A=(Q, Σ, Δ, q₀, F) which is an .

An UFA is such that, for all words w = a₁a₂ ... a_n, there exists at most one sequence of state r₀,r₁, ..., r_n, in Q with the following conditions:

1. r₀ = q₀
2. r_i+1 ∈ Δ(r_i, a_i+1), for i = 0, ..., n−1
3. r_n ∈ F.

In words, those conditions states 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.

Example

Let L be the set of words over the language {a,b} whose nth last letter is an a. The automaton in the figures accepts this language for n=2.

Deterministic automaton for the language L' for n=2

An Unambiguous finite autaton for (a+b)*a(a+b)^2.svg

The minimal DFA of L contains 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 remains. It is indeed unambigous as there exists only one nth last letter.

Some properties

The problems of universality, equivalence and inclusion for UFA belong to PTIME. It should be noted that those problem are PSPACE-Hard for NFA.

The cartesian product of two UFAs is an UFA.

References

• Christof Lödig, Unambiguous Finite Automata, Developments in Language Theory, (2013) pp29-30