Unambiguous finite automaton (original) (raw)
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.
| Property | Value |
|---|---|
| dbo: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) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Unambiguous_finite_automaton.svg?width=300 |
| dbo:wikiPageExternalLink | https://web.archive.org/web/20181231144045/https:/pdfs.semanticscholar.org/c3a8/bcd9d91f9255c5217755c8bbf2129a676460.pdf |
| dbo:wikiPageID | 48975671 (xsd:integer) |
| dbo:wikiPageLength | 8512 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1097193485 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Cartesian_product dbr:Nondeterministic_finite_automaton dbr:Deterministic_finite_automaton dbr:Monoid dbr:Dynamic_programming dbr:Alphabet_(formal_languages) dbc:Finite_automata dbr:PSPACE dbr:Formal_language dbr:Finite_state_transducer dbr:Automata_theory dbr:Semiring dbr:PTIME dbr:Fixpoint_algorithm dbr:N-tuple dbr:Weighted_automata dbr:File:Unambiguous_finite_autaton_for_(a b)*a(a b)^2.svg dbr:File:Unambiguous_finite_automaton.svg |
| dbp:wikiPageUsesTemplate | dbt:Main_article dbt:Prime dbt:Reflist dbt:Collapse_bottom dbt:Collapse_top dbt:Formal_languages_and_grammars |
| dct:subject | dbc:Finite_automata |
| gold:hypernym | dbr:Kind |
| 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) |
| rdfs:label | Eindeutiger endlicher Automat (de) Automate fini inambigu (fr) Unambiguous finite automaton (en) |
| owl:sameAs | yago-res:Unambiguous finite automaton wikidata:Unambiguous finite automaton dbpedia-de:Unambiguous finite automaton dbpedia-fa:Unambiguous finite automaton dbpedia-fr:Unambiguous finite automaton https://global.dbpedia.org/id/LjXZ |
| prov:wasDerivedFrom | wikipedia-en:Unambiguous_finite_automaton?oldid=1097193485&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Unambiguous_finite_autaton_for_(a b)*a(a b)^2.svg wiki-commons:Special:FilePath/Unambiguous_finite_automaton.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Unambiguous_finite_automaton |
| is dbo:wikiPageDisambiguates of | dbr:UFA |
| is dbo:wikiPageRedirects of | dbr:Unambiguous_finite_automata dbr:Unambiguous_automata dbr:Unambiguous_automaton |
| is dbo:wikiPageWikiLink of | dbr:Nondeterministic_finite_automaton dbr:Weighted_automaton dbr:State_complexity dbr:UFA dbr:Unambiguous_finite_automata dbr:Unambiguous_automata dbr:Unambiguous_automaton |
| is foaf:primaryTopic of | wikipedia-en:Unambiguous_finite_automaton |
