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.
| Attributes | Values |
|---|
| rdfs:label
| - Eindeutiger endlicher Automat (de)
- Automate fini inambigu (fr)
- Unambiguous finite automaton (en)
|
| rdfs:comment
| - Der eindeutige endliche Automat (englisch unambiguous finite automaton, UFA) nimmt seine Stellung zwischen dem deterministischen endlichen Automaten (DEA, engl. DFA) und dem nichtdeterministischen endlichen Automaten (NEA, engl. NFA) ein. Ein UFA ist im Grunde ein NFA, mit der Einschränkung, dass für jedes Eingabewort nur ein Weg durch die Zustände zu der Menge der akzeptierenden Zustände führen darf.Wie der NFA ist auch der UFA nichtdeterministisch und darf einen Zustand über mehrere Wege mit demselben Symbol verlassen. (de)
- 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. (en)
- En théorie des automates, un automate fini inambigu (on dit aussi non ambigu, en anglais « unambiguous finite automaton », abrégé en UFA) est un automate fini non déterministe d'un type particulier. C'est un automate qui, pour chaque mot accepté, ne possède qu'un seul calcul réussi. Tout automate fini déterministe est inambigu, mais la réciproque est fausse. Les trois types d'automates : non déterministe, inambigu, déterministe, reconnaissent les mêmes langages formels, à savoir les langages réguliers. (fr)
|
| foaf:depiction
| |
| dcterms:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| Link from a Wikipage to an external page
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| thumbnail
| |
| has abstract
| - Der eindeutige endliche Automat (englisch unambiguous finite automaton, UFA) nimmt seine Stellung zwischen dem deterministischen endlichen Automaten (DEA, engl. DFA) und dem nichtdeterministischen endlichen Automaten (NEA, engl. NFA) ein. Ein UFA ist im Grunde ein NFA, mit der Einschränkung, dass für jedes Eingabewort nur ein Weg durch die Zustände zu der Menge der akzeptierenden Zustände führen darf.Wie der NFA ist auch der UFA nichtdeterministisch und darf einen Zustand über mehrere Wege mit demselben Symbol verlassen. (de)
- En théorie des automates, un automate fini inambigu (on dit aussi non ambigu, en anglais « unambiguous finite automaton », abrégé en UFA) est un automate fini non déterministe d'un type particulier. C'est un automate qui, pour chaque mot accepté, ne possède qu'un seul calcul réussi. Tout automate fini déterministe est inambigu, mais la réciproque est fausse. Les trois types d'automates : non déterministe, inambigu, déterministe, reconnaissent les mêmes langages formels, à savoir les langages réguliers. Le nombre d'états d'un automate inambigu peut être exponentiellement plus petit qu'un automate déterministe équivalent. En contre-partie, certains problèmes sont plus difficiles à résoudre pour les automates inambigus que pour les automates déterministes. Par exemple, partant d'un automate A, un automate A' reconnaissant le complément du langage accepté par A se construit en temps linéaire si A est déterministe, mais il a été démontré qu'il ne peut être calculé en temps polynomial si A est inambigu. La notion d'automate inambigu se généralise à d'autres modèles de machines ou de calcul. Un présentation générale a été donnée par Thomas Colcombet. (fr)
- 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. (en)
|
| gold:hypernym
| |
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| is Link from a Wikipage to another Wikipage
of | |
| is Wikipage redirect
of | |
| is Wikipage disambiguates
of | |
| is foaf:primaryTopic
of | |
*a(a+b)%5E2.svg)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)
![[RDF Data]](/fct/images/sw-rdf-blue.png)