{"id":6387,"date":"2018-05-31T14:46:24","date_gmt":"2018-05-31T13:46:24","guid":{"rendered":"http:\/\/smart--grid.net\/?page_id=6387"},"modified":"2022-12-03T23:00:37","modified_gmt":"2022-12-03T22:00:37","slug":"construction-de-thompson","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/en\/language-theory\/construction-of-thompson\/","title":{"rendered":"Thompson Construction"},"content":{"rendered":"<div data-elementor-type=\"wp-page\" data-elementor-id=\"6387\" class=\"elementor elementor-6387\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-093efce elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"093efce\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-7a1ef3b\" data-id=\"7a1ef3b\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-b426b8c elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"b426b8c\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/complex-systems-ai.com\/en\/language-theory\/\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Language theory<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-c9d7681\" data-id=\"c9d7681\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-d6b5113 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"d6b5113\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/complex-systems-ai.com\/en\/\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Home page<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-ebdb023\" data-id=\"ebdb023\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-015a410 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"015a410\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/fr.wikipedia.org\/wiki\/Algorithme_de_Thompson\" target=\"_blank\" rel=\"noopener\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Wiki<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-7869a63 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"7869a63\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-f5976c7\" data-id=\"f5976c7\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-84ff33d elementor-widget elementor-widget-progress\" data-id=\"84ff33d\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"progress.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t<span class=\"elementor-title\" id=\"elementor-progress-bar-84ff33d\">\n\t\t\t\tDifficulty\t\t\t<\/span>\n\t\t\n\t\t<div aria-labelledby=\"elementor-progress-bar-84ff33d\" class=\"elementor-progress-wrapper\" role=\"progressbar\" aria-valuemin=\"0\" aria-valuemax=\"100\" aria-valuenow=\"50\" aria-valuetext=\"50% (Moyen)\">\n\t\t\t<div class=\"elementor-progress-bar\" data-max=\"50\">\n\t\t\t\t<span class=\"elementor-progress-text\">Average<\/span>\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-progress-percentage\">50%<\/span>\n\t\t\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-5138e982 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"5138e982\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-1f4e9706\" data-id=\"1f4e9706\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-7f9f3529 elementor-widget elementor-widget-text-editor\" data-id=\"7f9f3529\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t\n<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_82_2 counter-hierarchy ez-toc-counter ez-toc-grey ez-toc-container-direction\">\n<div class=\"ez-toc-title-container\">\n<p class=\"ez-toc-title\" style=\"cursor:inherit\">Contents<\/p>\n<span class=\"ez-toc-title-toggle\"><a href=\"#\" class=\"ez-toc-pull-right ez-toc-btn ez-toc-btn-xs ez-toc-btn-default ez-toc-toggle\" aria-label=\"Toggle Table of Content\"><span class=\"ez-toc-js-icon-con\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Toggle<\/span><span class=\"ez-toc-icon-toggle-span\"><svg style=\"fill: #999;color:#999\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" class=\"list-377408\" width=\"20px\" height=\"20px\" viewbox=\"0 0 24 24\" fill=\"none\"><path d=\"M6 6H4v2h2V6zm14 0H8v2h12V6zM4 11h2v2H4v-2zm16 0H8v2h12v-2zM4 16h2v2H4v-2zm16 0H8v2h12v-2z\" fill=\"currentColor\"><\/path><\/svg><svg style=\"fill: #999;color:#999\" class=\"arrow-unsorted-368013\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"10px\" height=\"10px\" viewbox=\"0 0 24 24\" version=\"1.2\" baseprofile=\"tiny\"><path d=\"M18.2 9.3l-6.2-6.3-6.2 6.3c-.2.2-.3.4-.3.7s.1.5.3.7c.2.2.4.3.7.3h11c.3 0 .5-.1.7-.3.2-.2.3-.5.3-.7s-.1-.5-.3-.7zM5.8 14.7l6.2 6.3 6.2-6.3c.2-.2.3-.5.3-.7s-.1-.5-.3-.7c-.2-.2-.4-.3-.7-.3h-11c-.3 0-.5.1-.7.3-.2.2-.3.5-.3.7s.1.5.3.7z\"\/><\/svg><\/span><\/span><\/span><\/a><\/span><\/div>\n<nav><ul class='ez-toc-list ez-toc-list-level-1' ><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/complex-systems-ai.com\/en\/language-theory\/construction-of-thompson\/#Construction-de-Thompson\" >Thompson Construction<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/complex-systems-ai.com\/en\/language-theory\/construction-of-thompson\/#Quelques-exemples-simples\" >Some simple examples<\/a><\/li><\/ul><\/nav><\/div>\n<h2><span class=\"ez-toc-section\" id=\"Construction-de-Thompson\"><\/span>Thompson Construction<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>Thompson&#039;s algorithm or Thompson&#039;s construction makes it possible to construct a <a href=\"https:\/\/complex-systems-ai.com\/en\/language-theory\/\">automaton<\/a> non-deterministic with epsilon-transition from a <a href=\"https:\/\/complex-systems-ai.com\/en\/language-theory\/regular-languages-and-regular-expressions\/\">regular expression<\/a>. The automaton is built recursively from basic patterns:<\/p>\n\n<p>Unit elements like \u2205, \u03b5 and a are recognized by<\/p>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img decoding=\"async\" class=\"alignnone wp-image-6389\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/05\/langage15.png\" alt=\"thompson construction\" width=\"108\" height=\"109\" title=\"\"><\/figure>\n<\/div>\n\n<p>We consider the operators of the regular expression R in decreasing order of exteriority. The outermost operator makes it possible to divide R in R1 | R2, R1.R2 or R1 * which are recognized by<\/p>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img fetchpriority=\"high\" decoding=\"async\" class=\"alignnone wp-image-6390\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/05\/langage16.png\" alt=\"thompson construction\" width=\"423\" height=\"202\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/05\/langage16.png 423w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/05\/langage16-300x143.png 300w\" sizes=\"(max-width: 423px) 100vw, 423px\" \/><\/figure>\n<\/div>\n\n<p>Here is an example of construction with the expression (a | b) (a \u2217 | ba \u2217 | b \u2217) \u2217<\/p>\n\n<p>We start the recursion by creating (A) (B) - the content is only indicative, we will see how to fill A and B as we go.<\/p>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img decoding=\"async\" class=\"alignnone wp-image-6391\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/05\/langage17.png\" alt=\"thompson construction\" width=\"976\" height=\"322\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/05\/langage17.png 976w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/05\/langage17-300x99.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/05\/langage17-768x253.png 768w\" sizes=\"(max-width: 976px) 100vw, 976px\" \/><\/figure>\n<\/div>\n\n<p>Then by placing the star on (B) * - here we take the opportunity to do the OR function in (A) = (a | b).<\/p>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-6392\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/05\/langage18.png\" alt=\"thompson construction\" width=\"971\" height=\"322\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/05\/langage18.png 971w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/05\/langage18-300x99.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/05\/langage18-768x255.png 768w\" sizes=\"(max-width: 971px) 100vw, 971px\" \/><\/figure>\n<\/div>\n\n<p>The next step is to do the OR function in (B) = (C | D | E)<\/p>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-6393\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/05\/langage19.png\" alt=\"thompson construction\" width=\"971\" height=\"322\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/05\/langage19.png 971w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/05\/langage19-300x99.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/05\/langage19-768x255.png 768w\" sizes=\"(max-width: 971px) 100vw, 971px\" \/><\/figure>\n<\/div>\n\n<p>The process contained by descending recursively until obtaining the final Thompson automaton.<\/p>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-6394\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/05\/langage20.png\" alt=\"thompson construction\" width=\"971\" height=\"322\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/05\/langage20.png 971w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/05\/langage20-300x99.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/05\/langage20-768x255.png 768w\" sizes=\"(max-width: 971px) 100vw, 971px\" \/><\/figure>\n<\/div>\n\n<p>The latter should then be determined and minimized for better reading.<\/p>\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Quelques-exemples-simples\"><\/span>Some simple examples<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n<ol class=\"wp-block-list\">\n<li>01<sup>\u2217<\/sup><\/li>\n<li>(0 + 1)01<\/li>\n<li>00(0 + 1)<sup>*<\/sup><\/li>\n<\/ol>\n\n<figure class=\"wp-block-image\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-6642\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/09\/langage59.png\" alt=\"thompson construction\" width=\"445\" height=\"510\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/09\/langage59.png 445w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/09\/langage59-262x300.png 262w\" sizes=\"(max-width: 445px) 100vw, 445px\" \/><\/figure>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<\/div>","protected":false},"excerpt":{"rendered":"<p>Language theory Home page Wiki Difficulty Medium 50% Thompson&#039;s construction Thompson&#039;s algorithm or Thompson&#039;s construction allows to build a non-deterministic automaton \u2026 <\/p>","protected":false},"author":1,"featured_media":0,"parent":5028,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-6387","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/6387","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/comments?post=6387"}],"version-history":[{"count":8,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/6387\/revisions"}],"predecessor-version":[{"id":18609,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/6387\/revisions\/18609"}],"up":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/5028"}],"wp:attachment":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/media?parent=6387"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}