Unambiguous finite automaton

In automata theory, an unambigous 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 exponentially quicker on DFA than on UFA. UFAs are a mix of both worlds; in some cases, they lead to smaller automata and quicker algorithms.

Formal definition

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:

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 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.

Example

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.

Deterministic automaton (DFA) for the language L for n=2

Unambiguous finite automaton (UFA) for the language L 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 unambigous as there exists only one nth last letter.

Some properties

• The problems of universality,^{[note 1]} equivalence,^{[note 2]} and inclusion^{[note 3]} for UFA belong to PTIME. Those problem are PSPACE-hard for general NFA.
• The cartesian product 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 unambigous, 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.
• For A an automaton with n states and a letter, it is decidable in time O(n²a) whether the automaton is unambiguous.

References

1. i.e.: given a UFA, does it accept every string at all?
2. i.e.: given two UFAs, do they accept the same set of strings?
3. i.e.: given two UFAs, does the second one accept each string accepted by the first?

• Christof Lödig, Unambiguous Finite Automata, Developments in Language Theory, (2013) pp.29-30 (Slides)