{"id":6350,"date":"2018-05-30T14:59:45","date_gmt":"2018-05-30T13:59:45","guid":{"rendered":"http:\/\/smart--grid.net\/?page_id=6350"},"modified":"2022-12-03T23:00:30","modified_gmt":"2022-12-03T22:00:30","slug":"automate-fini-deterministe","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/en\/language-theory\/deterministic-finite-automaton\/","title":{"rendered":"Deterministic finite automaton"},"content":{"rendered":"<div data-elementor-type=\"wp-page\" data-elementor-id=\"6350\" class=\"elementor elementor-6350\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-bd28137 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"bd28137\" 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-5890419\" data-id=\"5890419\" 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-467266a elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"467266a\" 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-b3a654e\" data-id=\"b3a654e\" 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-a1a02fd elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"a1a02fd\" 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-da6d236\" data-id=\"da6d236\" 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-bf03f70 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"bf03f70\" 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_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-d1b2d6f elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"d1b2d6f\" 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-057c587\" data-id=\"057c587\" 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-11bfc78 elementor-widget elementor-widget-progress\" data-id=\"11bfc78\" 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-11bfc78\">\n\t\t\t\tDifficulty\t\t\t<\/span>\n\t\t\n\t\t<div aria-labelledby=\"elementor-progress-bar-11bfc78\" 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-1a898c5b elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"1a898c5b\" 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-beb99c7\" data-id=\"beb99c7\" 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-3bae7cfc elementor-widget elementor-widget-text-editor\" data-id=\"3bae7cfc\" 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\/deterministic-finite-automaton\/#Automate-fini-deterministe\" >Deterministic finite automaton<\/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\/deterministic-finite-automaton\/#Lecture-dun-mot\" >Reading a word<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/complex-systems-ai.com\/en\/language-theory\/deterministic-finite-automaton\/#Du-langage-a-lautomate\" >From language to automaton<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-4\" href=\"https:\/\/complex-systems-ai.com\/en\/language-theory\/deterministic-finite-automaton\/#Des-automates-aux-mots-reconnus\" >Automatons with recognized words<\/a><\/li><\/ul><\/nav><\/div>\n<h2><span class=\"ez-toc-section\" id=\"Automate-fini-deterministe\"><\/span>Deterministic finite automaton<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> deterministic finite, by figuring 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<p><\/p>\n<figure class=\"wp-block-image\"><img fetchpriority=\"high\" decoding=\"async\" class=\"alignnone wp-image-6503\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/langage26.png\" alt=\"deterministic finite automaton\" width=\"780\" height=\"235\" title=\"\"><\/figure>\n<p><\/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 deterministic finite automaton A 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 \u2192 Q, is a partial application called the automaton transition function.<\/li>\n<\/ul>\n<\/div>\n<p><\/p>\n<p><\/p>\n<p>When T is total, in other words if there is in each state exactly one transition for any letter of the alphabet, the automaton is said to be complete.<\/p>\n<p><\/p>\n<p><\/p>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Lecture-dun-mot\"><\/span>Reading a word<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\n<p><\/p>\n<p>Note that the derivations produced by the reading of a word w by a deterministic finite automaton is linear and is therefore free of ambiguity: the reading of the letters composing the word causes well-defined transitions until it is blocked in the event of transitions. missing, or until reaching a certain state after the complete reading of the word. To check the reading of a word, it is necessary to start from the initial states and consume the symbols one by one while moving in the PLC until one has an impossible case or the complete reading of the word.<\/p>\n<p><\/p>\n<p><\/p>\n<p>We deduce the fundamental property of complete deterministic automata:<\/p>\n<p><\/p>\n<p><\/p>\n<div style=\"padding: 5px; background-color: #ffdcd3; border: 2px solid #ff7964; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\">\n<p>Let A = (Vt, Q, T) be a complete deterministic finite automaton. So, for any word u \u2208 V<sup>\u2217<\/sup><sub>t<\/sub> and any state q \u2208 Q, there exists a unique state q &#039;\u2208 Q such that q (u) \u2192 Aq&#039;.<\/p>\n<\/div>\n<p><\/p>\n<p><\/p>\n<p>In practice, it can be useful to make a PLC complete by adding a new state called trash to which all the missing transitions go. The blocking calculations then end up in the trash where they remain captured.<\/p>\n<p><\/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 deterministic automaton can also be defined with two additional data:<\/p>\n<ul>\n<li>of an initial state i \u2208 Q;<\/li>\n<li>of a set of accepting states F \u2286 Q;<\/li>\n<\/ul>\n<\/div>\n<p><\/p>\n<p><\/p>\n<p>Note that the initial state and the accepting states can also be deduced from the T rules.<\/p>\n<p><\/p>\n<p><\/p>\n<p>A word w is recognized by the automaton if there is a so-called successful calculation resulting from the initial state i and ending in an accepting state after having read the word w. We denote by L (A) the language of words recognized by the automaton A. A language recognized by an automaton is said to be recognizable. We denote by Rec the set of recognizable languages. Adding a trash state does not change the words recognized by a PLC.<\/p>\n<p><\/p>\n<p><\/p>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Du-langage-a-lautomate\"><\/span>From language to automaton<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\n<p><\/p>\n<div style=\"padding: 5px; background-color: #ffdcd3; border: 2px solid #ff7964; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\">\n<p>Any language accepted by a finite automaton is regular. All <a href=\"https:\/\/complex-systems-ai.com\/en\/language-theory\/regular-languages-and-regular-expressions\/\">regular language<\/a> is accepted by a finite automaton.<\/p>\n<\/div>\n<p><\/p>\n<p><\/p>\n<p>For each of the languages below, explain the language and draw a deterministic automaton that recognizes it.<\/p>\n<p><\/p>\n<p><\/p>\n<ul class=\"wp-block-list\">\n<li>L is the language denoted by aba + bab.<\/li>\n<li>L is the language denoted by (aba)<sup>\u2217<\/sup> + (bab)<sup>\u2217<\/sup>.<\/li>\n<li>L = {u \u2208 {a, b}<sup>\u2217<\/sup> such that u contains the factor bbb}.<\/li>\n<li>L = {u \u2208 {a, b}<sup>\u2217<\/sup> such that u does not contain the bbb factor<\/li>\n<\/ul>\n<p><\/p>\n<p><\/p>\n<figure class=\"wp-block-image size-large\"><img decoding=\"async\" class=\"alignnone\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/05\/langage4.png\" alt=\"deterministic finite automaton\" width=\"520\" height=\"288\" title=\"\"><\/figure>\n<p><\/p>\n<p><\/p>\n<p>We can effectively transform a <a href=\"https:\/\/complex-systems-ai.com\/en\/language-theory\/types-of-grammars\/\">grammar<\/a> regular on the right in a deterministic finite automaton and vice versa. The non-terminals correspond to the states of the automaton.<\/p>\n<p><\/p>\n<p><\/p>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Des-automates-aux-mots-reconnus\"><\/span>Automatons with recognized words<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\n<p><\/p>\n<p>Give all the words of length 0, 1, 2, 3 and 4 recognized by the following automata. This question can be answered systematically by using matrices. For this, we represent the automaton (which we can see as a <a href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-2\/\">graph<\/a>) by the adjacency matrix. Thus, the index coefficient i, j of the matrix M<sup>k<\/sup> corresponds to the words of length k recognized by the PLC, if the initial state was state i and the final state, state j. If we want to obtain the words of length k recognized by our automaton, it suffices to multiply the matrix by itself.<\/p>\n<p><\/p>\n<p><\/p>\n<figure class=\"wp-block-image size-large\"><img decoding=\"async\" class=\"alignnone\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/05\/langage5.png\" alt=\"deterministic finite automaton\" width=\"208\" height=\"153\" title=\"\"><\/figure>\n<p><\/p>\n<p><\/p>\n<p>We can symbolize (and even store) the transitions of a finite automaton in the form of a two-dimensional array. The lines represent the transition start states, the columns indicate the symbols and the values the transition destination states.<\/p>\n<p><\/p>\n<p><\/p>\n<p>For the automaton A, it suffices to evaluate (1,3) and (1,4) of the following matrices - indeed the recognized words start at state 1 and end in state 3 or 4:<\/p>\n<p><\/p>\n<p><\/p>\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/05\/langage6.png\" alt=\"deterministic finite automaton\" width=\"593\" height=\"177\" title=\"\"><\/figure>\n<p><\/p>\n<p><\/p>\n<p>Words of lengths 0: none; Words of lengths 1: b; Words of lengths 2: ab + aa + ba; Words of lengths 3: aba + abb + aaa + baa; Words of lengths 4: abaa + abab + abba + abbb + aaaa + baaa.<\/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% Deterministic finite automaton We usually draw a deterministic finite automaton, figuring the states \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-6350","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/6350","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=6350"}],"version-history":[{"count":5,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/6350\/revisions"}],"predecessor-version":[{"id":18587,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/6350\/revisions\/18587"}],"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=6350"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}