Thompson's construction (original) (raw)
تجربة بناء طومسون
| Property | Value |
|---|---|
| dbo:abstract | تجربة بناء طومسون (ar) El algoritmo Thompson (también conocido como método de Thompson) creado por Ken Thompson y Dennis Ritchie, sirve para obtener autómatas finitos no deterministas con transiciones vacías (AFND-ε) a partir de expresiones regulares (ER). (es) En informatique théorique plus précisément en théorie des langages, l'algorithme de Thompson est un algorithme qui, étant donnée une expression régulière, crée un automate fini qui reconnaît le langage décrit par cette expression. Il est nommé ainsi d'après Ken Thompson qui l'a décrit en 1968. (fr) In computer science, Thompson's construction algorithm, also called the McNaughton–Yamada–Thompson algorithm, is a method of transforming a regular expression into an equivalent nondeterministic finite automaton (NFA). This NFA can be used to match strings against the regular expression. This algorithm is credited to Ken Thompson. Regular expressions and nondeterministic finite automata are two representations of formal languages. For instance, text processing utilities use regular expressions to describe advanced search patterns, but NFAs are better suited for execution on a computer. Hence, this algorithm is of practical interest, since it can compile regular expressions into NFAs. From a theoretical point of view, this algorithm is a part of the proof that they both accept exactly the same languages, that is, the regular languages. An NFA can be made deterministic by the powerset construction and then be minimized to get an optimal automaton corresponding to the given regular expression. However, an NFA may also be interpreted directly. To decide whether two given regular expressions describe the same language, each can be converted into an equivalent minimal deterministic finite automaton via Thompson's construction, powerset construction, and DFA minimization. If, and only if, the resulting automata agree up to renaming of states, the regular expressions' languages agree. (en) L'algoritmo di Thompson o algoritmo di costruzione (spesso indicato con (TCA) dall'inglese Thompson's Construction Algorithm) è un algoritmo che deriva un automa a stati finiti non deterministico (NFA) da una qualunque espressione regolare dividendola nelle sue sottoespressioni elementari, che possono essere convertite direttamente per mezzo di un insieme di regole. L'algoritmo è stato inventato da Ken Thompson. (it) O Algoritmo de Thompson, criado por Ken Thompson e Dennis Ritchie, serve para construir Autômatos finitos não determinísticos a partir de uma Expressão Regular. Em ciência da computação, Algoritmo de Thompson é um algoritmo para transformar uma expressão regular em um equivalente autômato finito não determinístico (AFN). Este AFN pode ser usado para casar palavras com expressões regulares. Expressão regular e autômato finito não-determinístico são duas representações abstratas de linguagens formais.Enquanto expressões regulares são utilizadas, por exemplo, para descrever padrões avançados de pesquisa em " localizar e substituir " -como operações de utilidades de processamento de texto, o formato do AFN é mais adequado para a execução em um computador. Assim, estealgoritmo é de interesse prático , uma vez que pode ser considerado como um compilador de expressão regular para AFN. Em um ponto de vista mais teórico, esse algoritmo é uma parte da prova que ambos aceitam exatamente as mesmas linguagens, isto é, as linguagens regulares. Um automato obtido assim pode ser feito deterministicamente pela Construção do conjunto das partes e, em seguida, ser minimizado para obter um automato ótimo correspondente à expressão regular , mas também pode ser utilizado diretamente. (pt) Задача синтезу скінченного автомата полягає в створенні такого автомата акцептора, який би розпізнавав дану регулярну мову. (uk) 汤普森构造法在计算机科学中是指一个能将正则表达式转化为一个与之等价的非确定有限状态自动机（NFA）的算法。算法得到的NFA可以在编程中用于匹配一个正则表达式，这也是正则表达式引擎实现的基本思路之一。 正则表达式和非确定有限状态自动机是形式语言的两种不同的抽象表达方式。在诸如文本编辑器的高级“查找和替换”以及许多编程语言中，人们都习惯使用正则表达式来表示字符串的匹配模式。然而，当计算机执行匹配程序时，NFA却是更加适合的一种格式。因此，汤普森构造法有着重要的应用价值，它实际上可以视作正则表达式到NFA的一个编译器。而从理论角度上来说，该算法实际上是正则表达式和NFA等价性证明的一部分——事实上，这两种表述形式本质上都对应着相同的语言，即正则语言。 在应用中，算法得到的NFA可以再次通过幂集构造和最小化的过程得到一个对应的最简的确定有限状态自动机（DFA），进而用于匹配正则表达式。但是有些情况下也会直接使用对应的NFA。 (zh) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Thompson-epsilon.svg?width=300 |
| dbo:wikiPageID | 37187592 (xsd:integer) |
| dbo:wikiPageLength | 13275 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1121376147 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Powerset_construction dbr:Nondeterministic_finite_automaton dbr:Deterministic_finite_automaton dbr:Algorithm dbr:Regular_expression dbr:Compiler dbr:Mathematical_induction dbr:Glushkov's_construction_algorithm dbr:Computer_science dbr:DFA_minimization dbc:Finite_automata dbr:Formal_language dbr:Regular_language dbr:Ken_Thompson dbr:Recursively dbr:Kleene's_algorithm dbr:Kleene_star dbr:Pattern_matching dbr:Up_to dbr:Text_processing dbr:File:Small-thompson-example.svg dbr:File:Thompson's_construction_algorithm...ression_for_binary_multiples_of_3.gif dbr:File:Thompson-a-symbol.svg dbr:File:Thompson-concat.svg dbr:File:Thompson-epsilon.svg dbr:File:DFA_example_multiplies_of_3.svg dbr:File:Thompson-or.svg dbr:File:Thompson-kleene-star.svg |
| dbp:date | February 2021 (en) |
| dbp:reason | a transition function «math»\Delta«/math» : «math»Q\times\Sigma \rightarrow P«/math» in the foreign notation of the NFA main article (en) |
| dbp:wikiPageUsesTemplate | dbt:! dbt:Better_source_needed dbt:Clarification_needed dbt:Code dbt:Color dbt:Commons_category dbt:Math dbt:Mvar dbt:Nowrap_begin dbt:Nowrap_end dbt:Reflist dbt:Short_description dbt:Strings |
| dct:subject | dbc:Finite_automata |
| gold:hypernym | dbr:Algorithm |
| rdf:type | dbo:Software |
| rdfs:comment | تجربة بناء طومسون (ar) El algoritmo Thompson (también conocido como método de Thompson) creado por Ken Thompson y Dennis Ritchie, sirve para obtener autómatas finitos no deterministas con transiciones vacías (AFND-ε) a partir de expresiones regulares (ER). (es) En informatique théorique plus précisément en théorie des langages, l'algorithme de Thompson est un algorithme qui, étant donnée une expression régulière, crée un automate fini qui reconnaît le langage décrit par cette expression. Il est nommé ainsi d'après Ken Thompson qui l'a décrit en 1968. (fr) L'algoritmo di Thompson o algoritmo di costruzione (spesso indicato con (TCA) dall'inglese Thompson's Construction Algorithm) è un algoritmo che deriva un automa a stati finiti non deterministico (NFA) da una qualunque espressione regolare dividendola nelle sue sottoespressioni elementari, che possono essere convertite direttamente per mezzo di un insieme di regole. L'algoritmo è stato inventato da Ken Thompson. (it) Задача синтезу скінченного автомата полягає в створенні такого автомата акцептора, який би розпізнавав дану регулярну мову. (uk) 汤普森构造法在计算机科学中是指一个能将正则表达式转化为一个与之等价的非确定有限状态自动机（NFA）的算法。算法得到的NFA可以在编程中用于匹配一个正则表达式，这也是正则表达式引擎实现的基本思路之一。 正则表达式和非确定有限状态自动机是形式语言的两种不同的抽象表达方式。在诸如文本编辑器的高级“查找和替换”以及许多编程语言中，人们都习惯使用正则表达式来表示字符串的匹配模式。然而，当计算机执行匹配程序时，NFA却是更加适合的一种格式。因此，汤普森构造法有着重要的应用价值，它实际上可以视作正则表达式到NFA的一个编译器。而从理论角度上来说，该算法实际上是正则表达式和NFA等价性证明的一部分——事实上，这两种表述形式本质上都对应着相同的语言，即正则语言。 在应用中，算法得到的NFA可以再次通过幂集构造和最小化的过程得到一个对应的最简的确定有限状态自动机（DFA），进而用于匹配正则表达式。但是有些情况下也会直接使用对应的NFA。 (zh) In computer science, Thompson's construction algorithm, also called the McNaughton–Yamada–Thompson algorithm, is a method of transforming a regular expression into an equivalent nondeterministic finite automaton (NFA). This NFA can be used to match strings against the regular expression. This algorithm is credited to Ken Thompson. An NFA can be made deterministic by the powerset construction and then be minimized to get an optimal automaton corresponding to the given regular expression. However, an NFA may also be interpreted directly. (en) O Algoritmo de Thompson, criado por Ken Thompson e Dennis Ritchie, serve para construir Autômatos finitos não determinísticos a partir de uma Expressão Regular. Em ciência da computação, Algoritmo de Thompson é um algoritmo para transformar uma expressão regular em um equivalente autômato finito não determinístico (AFN). Este AFN pode ser usado para casar palavras com expressões regulares. (pt) |
| rdfs:label | تجربة بناء طومسون (ar) Algoritmo de Thompson (es) Algorithme de Thompson (fr) Algoritmo di Thompson (it) Algoritmo de Thompson (pt) Thompson's construction (en) Синтез скінченних автоматів (uk) 汤普森构造法 (zh) |
| owl:sameAs | freebase:Thompson's construction yago-res:Thompson's construction wikidata:Thompson's construction dbpedia-ar:Thompson's construction dbpedia-es:Thompson's construction dbpedia-fa:Thompson's construction dbpedia-fr:Thompson's construction dbpedia-it:Thompson's construction dbpedia-pt:Thompson's construction dbpedia-ro:Thompson's construction dbpedia-uk:Thompson's construction dbpedia-zh:Thompson's construction https://global.dbpedia.org/id/4wZ1M |
| prov:wasDerivedFrom | wikipedia-en:Thompson's_construction?oldid=1121376147&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Thompson-kleene-star.svg wiki-commons:Special:FilePath/Small-thompson-example.svg wiki-commons:Special:FilePath/Thompson's_constructi...ression_for_binary_multiples_of_3.gif wiki-commons:Special:FilePath/Thompson-a-symbol.svg wiki-commons:Special:FilePath/Thompson-concat.svg wiki-commons:Special:FilePath/Thompson-epsilon.svg wiki-commons:Special:FilePath/DFA_example_multiplies_of_3.svg wiki-commons:Special:FilePath/Thompson-or.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Thompson's_construction |
| is dbo:wikiPageRedirects of | dbr:Thompson's_construction_algorithm dbr:McNaughton-Yamada-Thompson_algorithm dbr:McNaughton–Yamada–Thompson_algorithm dbr:Thompson_NFA |
| is dbo:wikiPageWikiLink of | dbr:Nondeterministic_finite_automaton dbr:Regular_expression dbr:Thompson's_construction_algorithm dbr:Tagged_Deterministic_Finite_Automaton dbr:Matching_wildcards dbr:Ken_Thompson dbr:McNaughton-Yamada-Thompson_algorithm dbr:McNaughton–Yamada–Thompson_algorithm dbr:Ragel dbr:Thompson_NFA |
| is foaf:primaryTopic of | wikipedia-en:Thompson's_construction |
