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.
Wikipage disambiguates
Wikipage redirect
primaryTopic
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.
has abstract
Der eindeutige endliche Automa ...... it demselben Symbol verlassen.
@de
En théorie des automates, un a ...... polynomial si A est inambigu.
@fr
In automata theory, an unambig ...... d quicker algorithms than NFA.
@en
Link from a Wikipage to an external page
Wikipage page ID
48,975,671
Wikipage revision ID
723,929,682
subject
hypernym
comment
Der eindeutige endliche Automa ...... it demselben Symbol verlassen.
@de
En théorie des automates, un a ...... savoir les langages réguliers.
@fr
In automata theory, an unambig ...... d quicker algorithms than NFA.
@en
label
Automate fini inambigu
@fr
Eindeutiger endlicher Automat
@de
Unambiguous finite automaton
@en
