Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Unambiguous finite automaton
Summary
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, 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, .
An UFA is an NFA such that, for each word , there exists at most one sequence of states , in with the following conditions:
ri+1 ∈ Δ(ri, ai+1), for i = 0, ..., n−1 for
In words, those conditions state that, if is accepted by , there is exactly one accepting path, that is, one path from an initial state to a final state, labelled by .
Let be the set of words over the alphabet {a,b} whose nth last letter is an . The figures show a DFA and a UFA accepting this language for n=2.
The minimal DFA accepting has 2n states, one for each subset of {1...n}. There is an UFA of states which accepts : it guesses the nth last letter, and then verifies that only 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 UFA's language is a subset of another UFA's language.
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.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.