{"id":6377,"date":"2018-05-31T10:36:31","date_gmt":"2018-05-31T09:36:31","guid":{"rendered":"http:\/\/smart--grid.net\/?page_id=6377"},"modified":"2022-12-03T23:00:32","modified_gmt":"2022-12-03T22:00:32","slug":"automate-avec-transition-vide","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/en\/language-theory\/automaton-with-empty-transition\/","title":{"rendered":"PLC with empty transition"},"content":{"rendered":"<div data-elementor-type=\"wp-page\" data-elementor-id=\"6377\" class=\"elementor elementor-6377\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-28c9fc4 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"28c9fc4\" 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-fbc1925\" data-id=\"fbc1925\" 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-06655e2 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"06655e2\" 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-0c89454\" data-id=\"0c89454\" 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-5cac201 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"5cac201\" 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-b557c05\" data-id=\"b557c05\" 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-6a72dc7 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"6a72dc7\" 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\/Automate_fini_non_d%C3%A9terministe\" 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-996fbed elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"996fbed\" 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-f3578c8\" data-id=\"f3578c8\" 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-d13815e elementor-widget elementor-widget-progress\" data-id=\"d13815e\" 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-d13815e\">\n\t\t\t\tDifficulty\t\t\t<\/span>\n\t\t\n\t\t<div aria-labelledby=\"elementor-progress-bar-d13815e\" class=\"elementor-progress-wrapper\" role=\"progressbar\" aria-valuemin=\"0\" aria-valuemax=\"100\" aria-valuenow=\"25\" aria-valuetext=\"25% (Facile)\">\n\t\t\t<div class=\"elementor-progress-bar\" data-max=\"25\">\n\t\t\t\t<span class=\"elementor-progress-text\">Easy<\/span>\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-progress-percentage\">25%<\/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-6c1503a6 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"6c1503a6\" 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-1c25db91\" data-id=\"1c25db91\" 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-54701ae1 elementor-widget elementor-widget-text-editor\" data-id=\"54701ae1\" 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<p><\/p>\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\/automaton-with-empty-transition\/#Automate-avec-transition-vide\" >PLC with empty transition<\/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\/automaton-with-empty-transition\/#De-lautomate-avec-transition-vide-aux-mots-reconnus\" >From PLC with empty transition to recognized words<\/a><\/li><\/ul><\/nav><\/div>\n<h2><span class=\"ez-toc-section\" id=\"Automate-avec-transition-vide\"><\/span>PLC with empty transition<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>We are used to drawing a <a href=\"https:\/\/complex-systems-ai.com\/en\/language-theory\/\">automaton<\/a> with empty transition, by representing the states by circles, by indicating the initial state by an incoming arrow, the accepting states by a double circle or an outgoing arrow, and the transition from state q to state q&#039; by reading the letter \u03b1 by an arrow going from q to q&#039; and labeled by \u03b1.<\/p>\n<p><\/p>\n<div style=\"padding: 5px; background-color: #d5edff; border: 2px solid #3c95e8; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\">\n<p>A finite automaton A with epsilon transition (or automaton with empty transition) is a triplet (Vt, Q, T) where<\/p>\n<ul>\n<li>Vt is the vocabulary of the automaton;<\/li>\n<li>Q is the finite set of states of the automaton;<\/li>\n<li>T: Q \u00d7 (Vt \u222a \u03b5) \u2192 Q, is a partial map called the automaton transition function.<\/li>\n<\/ul>\n<\/div>\n<p><\/p>\n<p>Note that the notation q (\u03b1) \u2192 q &#039;becomes ambiguous, since it now takes two different meanings depending on whether \u03b1 is considered as a letter (or as the symbol \u03b5) and there will then be a single transition, or as a word (of length 1 or 0), and there can then be an arbitrary number of transitions (of which at most one will be non-empty).<\/p>\n<p><\/p>\n<p>Again, the notions of derivation is unchanged, and that of derivation tree<br \/>requires only a trivial adaptation, since there are now transitions labeled by \u03b5. The calculations of an automaton with empty transitions allow the passage through any number of empty transitions during execution. The number of states scanned will therefore no longer be equal to the number of letters in the input word but may be much greater. The calculation tree of an automaton with empty transitions turns out to be a less interesting tool than for non-deterministic automata without empty transitions.<\/p>\n<p><\/p>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"De-lautomate-avec-transition-vide-aux-mots-reconnus\"><\/span>From PLC with empty transition to recognized words<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\n<p>The process is the same as the tree created by a non-deterministic automaton. Let us note that in addition to having to create new branches in the event of indeterminism, it is also necessary to go through the transitions of the successor states by epsilon-transition.<\/p>\n<p><\/p>\n<p>If we take the above automaton on the word aaaab:<\/p>\n<p><\/p>\n<p>p (aaaab) \u2192 q (aaab) \u2192 r (aaab) \u2192 s (aaab) \u2192 s (aab) \u2192 s (ab) \u2192 s (b) \u2192 q (b) \u2192 r - terminal state<\/p>\n<p><\/p>\n<p>It is complex to calculate the words of length n recognized by a PLC with epsilon transition, it is then necessary to close the PLC.<\/p>\n<p><\/p>\n<p>The principle of the algorithm consists in replacing each path of length 1 starting with an epsilon-transition by a new transition which describes this path.<\/p>\n<p><\/p>\n<div>\n<figure><img fetchpriority=\"high\" decoding=\"async\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/05\/langage13.png\" alt=\"PLC with empty transition\" width=\"400\" height=\"171\" title=\"\"><\/figure>\n<\/div>\n<p><\/p>\n<p>There are two paths of length 1 which start with the transition on epsilon:<\/p>\n<p><\/p>\n<ul class=\"wp-block-list\">\n<li>(1, \u03b5, 3) (3, b, 3)<\/li>\n<li>\u00a0(1, \u03b5, 3) (3, c, 4)<\/li>\n<\/ul>\n<p><\/p>\n<p>We add to the automaton two new transitions which summarize these two paths:<\/p>\n<p><\/p>\n<ul class=\"wp-block-list\">\n<li>(1, b, 3)<\/li>\n<li>(1, c, 4)<\/li>\n<\/ul>\n<p><\/p>\n<p>And we remove the transition (1, \u03b5, 3).<\/p>\n<p><\/p>\n<div>\n<figure><img decoding=\"async\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/05\/langage14.png\" alt=\"PLC with empty transition\" width=\"373\" height=\"220\" title=\"\"><\/figure>\n<\/div>\n<p><\/p>\n<p>The algorithm is a little more complex in the cases where several epsilon-transitions follow one another and if they go into a final state, but the general principle presented here remains valid (it is enough to apply the first step).<\/p>\n<p><\/p>\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 Easy 25% Automaton with empty transition We usually draw an automaton with empty transition, figuring \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-6377","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/6377","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=6377"}],"version-history":[{"count":3,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/6377\/revisions"}],"predecessor-version":[{"id":18598,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/6377\/revisions\/18598"}],"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=6377"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}