Powerset construction (original) (raw)
Die Potenzmengenkonstruktion (Myhill-Konstruktion oder auch Teilmengenkonstruktion) ist ein Verfahren, das einen nichtdeterministischen endlichen Automaten (NEA) in einen äquivalenten deterministischen endlichen Automaten (DEA) umwandelt. Das Verfahren dient als konstruktiver Beweis für die Äquivalenz der beiden Automatenmodelle.
| Property | Value |
|---|---|
| dbo:abstract | Die Potenzmengenkonstruktion (Myhill-Konstruktion oder auch Teilmengenkonstruktion) ist ein Verfahren, das einen nichtdeterministischen endlichen Automaten (NEA) in einen äquivalenten deterministischen endlichen Automaten (DEA) umwandelt. Das Verfahren dient als konstruktiver Beweis für die Äquivalenz der beiden Automatenmodelle. (de) En informatique théorique, et notamment en théorie des automates, l'algorithme appelé la construction par sous-ensembles, en anglais « powerset construction » ou « subset construction », est la méthode usuelle pour convertir un automate fini non déterministe (abrégé en « AFN ») en un automate fini déterministe (abrégé en « AFD ») équivalent, c'est-à-dire qui reconnaît le même langage rationnel. L'existence même d'une conversion, et l'existence d'un algorithme pour la réaliser, est remarquable et utile. Elle est remarquable parce qu'il existe peu de modèles de machines pour lesquels les versions déterministe et non déterministe ont la même puissance de reconnaissance : ainsi, les automates à pile déterministes sont moins puissants que les automates à pile généraux. Elle est utile dans la pratique parce que la reconnaissance par un automate déterministe est bien plus facile à mettre en œuvre que la reconnaissance par automate non déterministe. Toutefois, la construction par sous-ensembles peut produire un automate dont la taille, mesurée en nombre d'états, est exponentielle par rapport à la taille de l'automate de départ. La construction par sous-ensembles a été publiée pour la première fois par Michael O. Rabin et Dana S. Scott dans un article fondateur paru en 1959. Ils ont obtenu le prix Turing pour leurs travaux autour du non-déterminisme en 1976. (fr) En la teoría de la computación, la construcción de conjunto potencia es un método estándar para convertir un autómata finito no determinista (AFND) a un autómata finito determinista (AFD) que reconoce el mismo lenguaje formal. En la teoría es importante porque establece que los AFNDs aunque son más flexibles, no pueden reconocer ningún lenguaje que un AFD no pueda reconocer. También es importante porque se puede usar para convertir un AFND que es más fácil de construir a un AFD que es más fácil de ejecutar. Sin embargo si el AFND tiene estados, el AFD resultante podría tener hasta estados, exponencialmente más. Eso resulta que a veces construir un AFD de un AFND grande no es practicable. * Datos: Q2106494 (es) In the theory of computation and automata theory, the powerset construction or subset construction is a standard method for converting a nondeterministic finite automaton (NFA) into a deterministic finite automaton (DFA) which recognizes the same formal language. It is important in theory because it establishes that NFAs, despite their additional flexibility, are unable to recognize any language that cannot be recognized by some DFA. It is also important in practice for converting easier-to-construct NFAs into more efficiently executable DFAs. However, if the NFA has n states, the resulting DFA may have up to 2n states, an exponentially larger number, which sometimes makes the construction impractical for large NFAs. The construction, sometimes called the Rabin–Scott powerset construction (or subset construction) to distinguish it from similar constructions for other types of automata, was first published by Michael O. Rabin and Dana Scott in 1959. (en) Determinizacja automatu skończonego – proces tworzenia deterministycznego automatu skończonego (DAS) z niedeterministycznego automatu skończonego (NAS). Transformacja taka jest zawsze możliwa i otrzymany w jej procesie automat akceptuje dokładnie ten sam język, co automat wejściowy. Jakkolwiek, gdy NAS ma stanów, wynikowy DAS może mieć do stanów, wykładniczo więcej, co czyni proces niepraktycznym dla dużych NAS. (pl) Nella teoria dei linguaggi formali, la costruzione dei sottoinsiemi o costruzione per sottoinsiemi o subset construction è la tecnica di costruzione dell'automa a stati finiti deterministico equivalente ad un automa a stati finiti non deterministico. (it) 在计算理论中，幂集构造是转换非确定有限状态自动机（NFA）到识别同样语言的确定有限状态自动机（DFA）的标准方法。它在理论上的重要性源于它确立了NFA尽管有额外的灵活性，它不能识别不能被任何DFA识别的任何语言。在实践中的重要性源于它把易于构造的NFA转换成了更有效执行的DFA。但是如果NFA有n个状态，结果的DFA可能有最多2n个状态，这种指数增长有时使这种构造对于大NFA而言是不实际的。 (zh) Детермінізація недетермінованого скінченного автомата — полягає в перетворенні недетермінованого скінченного автомату на еквівалентний (тобто такий, що розпізнає таку ж формальну мову) детермінований скінченний автомат. (uk) |
| dbo:thumbnail | wiki-commons:Special:FilePath/NFA-powerset-construction-example.svg?width=300 |
| dbo:wikiPageExternalLink | https://books.google.com/books%3Fid=ikS8BLdLDxIC&pg=PA43 |
| dbo:wikiPageID | 1163167 (xsd:integer) |
| dbo:wikiPageLength | 12359 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1121421610 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Power_set dbr:Natural_language_processing dbr:Nondeterministic_finite_automaton dbr:Deterministic_finite_automaton dbr:Worst-case_complexity dbr:Reflexive_transitive_closure dbr:Theory_of_computation dbr:Büchi_automaton dbr:Tuple dbr:DFA_minimization dbr:Dana_Scott dbc:Finite_automata dbr:Formal_language dbr:Ω-automaton dbr:Automata_theory dbr:Michael_O._Rabin dbr:Muller_automaton dbr:Substring dbr:Safra's_construction dbr:File:DFA-powerset-construction-example.svg dbr:File:NFA-powerset-construction-example.svg dbr:File:NFA_and_blown-up_equivalent_DFA_01.svg |
| dbp:wikiPageUsesTemplate | dbt:Cite_book dbt:Main_article dbt:Math dbt:Mvar dbt:R dbt:Reflist dbt:Short_description dbt:Pipe |
| dct:subject | dbc:Finite_automata |
| gold:hypernym | dbr:Method |
| rdf:type | dbo:Software yago:Abstraction100002137 yago:Communication100033020 yago:Language106282651 yago:WikicatFormalLanguages |
| rdfs:comment | Die Potenzmengenkonstruktion (Myhill-Konstruktion oder auch Teilmengenkonstruktion) ist ein Verfahren, das einen nichtdeterministischen endlichen Automaten (NEA) in einen äquivalenten deterministischen endlichen Automaten (DEA) umwandelt. Das Verfahren dient als konstruktiver Beweis für die Äquivalenz der beiden Automatenmodelle. (de) Determinizacja automatu skończonego – proces tworzenia deterministycznego automatu skończonego (DAS) z niedeterministycznego automatu skończonego (NAS). Transformacja taka jest zawsze możliwa i otrzymany w jej procesie automat akceptuje dokładnie ten sam język, co automat wejściowy. Jakkolwiek, gdy NAS ma stanów, wynikowy DAS może mieć do stanów, wykładniczo więcej, co czyni proces niepraktycznym dla dużych NAS. (pl) Nella teoria dei linguaggi formali, la costruzione dei sottoinsiemi o costruzione per sottoinsiemi o subset construction è la tecnica di costruzione dell'automa a stati finiti deterministico equivalente ad un automa a stati finiti non deterministico. (it) 在计算理论中，幂集构造是转换非确定有限状态自动机（NFA）到识别同样语言的确定有限状态自动机（DFA）的标准方法。它在理论上的重要性源于它确立了NFA尽管有额外的灵活性，它不能识别不能被任何DFA识别的任何语言。在实践中的重要性源于它把易于构造的NFA转换成了更有效执行的DFA。但是如果NFA有n个状态，结果的DFA可能有最多2n个状态，这种指数增长有时使这种构造对于大NFA而言是不实际的。 (zh) Детермінізація недетермінованого скінченного автомата — полягає в перетворенні недетермінованого скінченного автомату на еквівалентний (тобто такий, що розпізнає таку ж формальну мову) детермінований скінченний автомат. (uk) En la teoría de la computación, la construcción de conjunto potencia es un método estándar para convertir un autómata finito no determinista (AFND) a un autómata finito determinista (AFD) que reconoce el mismo lenguaje formal. En la teoría es importante porque establece que los AFNDs aunque son más flexibles, no pueden reconocer ningún lenguaje que un AFD no pueda reconocer. También es importante porque se puede usar para convertir un AFND que es más fácil de construir a un AFD que es más fácil de ejecutar. Sin embargo si el AFND tiene estados, el AFD resultante podría tener hasta estados, exponencialmente más. Eso resulta que a veces construir un AFD de un AFND grande no es practicable. (es) In the theory of computation and automata theory, the powerset construction or subset construction is a standard method for converting a nondeterministic finite automaton (NFA) into a deterministic finite automaton (DFA) which recognizes the same formal language. It is important in theory because it establishes that NFAs, despite their additional flexibility, are unable to recognize any language that cannot be recognized by some DFA. It is also important in practice for converting easier-to-construct NFAs into more efficiently executable DFAs. However, if the NFA has n states, the resulting DFA may have up to 2n states, an exponentially larger number, which sometimes makes the construction impractical for large NFAs. (en) En informatique théorique, et notamment en théorie des automates, l'algorithme appelé la construction par sous-ensembles, en anglais « powerset construction » ou « subset construction », est la méthode usuelle pour convertir un automate fini non déterministe (abrégé en « AFN ») en un automate fini déterministe (abrégé en « AFD ») équivalent, c'est-à-dire qui reconnaît le même langage rationnel. (fr) |
| rdfs:label | Potenzmengenkonstruktion (de) Construcción de conjunto potencia (es) Costruzione dei sottoinsiemi (it) Construction par sous-ensembles (fr) Powerset construction (en) Determinizacja automatu skończonego (pl) Conversão AFN AFD (pt) Детермінізація НДСкА (uk) 幂集构造 (zh) |
| owl:sameAs | freebase:Powerset construction yago-res:Powerset construction wikidata:Powerset construction dbpedia-de:Powerset construction dbpedia-es:Powerset construction dbpedia-fa:Powerset construction dbpedia-fr:Powerset construction dbpedia-it:Powerset construction dbpedia-pl:Powerset construction dbpedia-pt:Powerset construction dbpedia-th:Powerset construction dbpedia-uk:Powerset construction dbpedia-zh:Powerset construction https://global.dbpedia.org/id/zFBM |
| prov:wasDerivedFrom | wikipedia-en:Powerset_construction?oldid=1121421610&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/DFA-powerset-construction-example.svg wiki-commons:Special:FilePath/NFA-powerset-construction-example.svg wiki-commons:Special:FilePath/NFA_and_blown-up_equivalent_DFA_01.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Powerset_construction |
| is dbo:knownFor of | dbr:Dana_Scott dbr:Michael_O._Rabin |
| is dbo:wikiPageRedirects of | dbr:Nondeterministic_finite_state_machine/Proofs dbr:Rabin-Scott_powerset_construction dbr:Subset_construction_algorithm dbr:Determinization dbr:Determinization_of_Automaton dbr:Determinization_of_automata dbr:Determinization_of_automaton dbr:NDFA_to_DFA_conversion_algorithm dbr:NFA_to_DFA_Conversion dbr:NFA_to_DFA_conversion dbr:Power_set_construction dbr:Subset_construction |
| is dbo:wikiPageWikiLink of | dbr:List_of_algorithms dbr:Nondeterministic_finite_automaton dbr:Nondeterministic_finite_state_machine/Proofs dbr:Deterministic_finite_automaton dbr:Regular_expression dbr:Deterministic_automaton dbr:Generalized_nondeterministic_finite_automaton dbr:Timeline_of_algorithms dbr:Glushkov's_construction_algorithm dbr:Thompson's_construction dbr:Tagged_Deterministic_Finite_Automaton dbr:Garden_of_Eden_(cellular_automaton) dbr:DFA_minimization dbr:Dana_Scott dbr:Finite-state_transducer dbr:Michael_O._Rabin dbr:Finite-state_machine dbr:Nondeterministic_algorithm dbr:Rabin-Scott_powerset_construction dbr:String-searching_algorithm dbr:Subset_construction_algorithm dbr:Determinization dbr:Determinization_of_Automaton dbr:Determinization_of_automata dbr:Determinization_of_automaton dbr:NDFA_to_DFA_conversion_algorithm dbr:NFA_to_DFA_Conversion dbr:NFA_to_DFA_conversion dbr:Power_set_construction dbr:Subset_construction |
| is dbp:knownFor of | dbr:Michael_O._Rabin |
| is foaf:primaryTopic of | wikipedia-en:Powerset_construction |
