{"id":6358,"date":"2018-05-31T10:13:41","date_gmt":"2018-05-31T09:13:41","guid":{"rendered":"http:\/\/smart--grid.net\/?page_id=6358"},"modified":"2022-12-03T23:00:30","modified_gmt":"2022-12-03T22:00:30","slug":"automate-fini-non-deterministe","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/en\/language-theory\/non-deterministic-finite-automaton\/","title":{"rendered":"Non-deterministic finite automaton"},"content":{"rendered":"<div data-elementor-type=\"wp-page\" data-elementor-id=\"6358\" class=\"elementor elementor-6358\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-793f198 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"793f198\" 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-e2035fa\" data-id=\"e2035fa\" 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-4f455f5 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"4f455f5\" 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-b38f307\" data-id=\"b38f307\" 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-dcb5f1d elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"dcb5f1d\" 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-2327628\" data-id=\"2327628\" 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-e1d8a32 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"e1d8a32\" 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-f7c9104 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"f7c9104\" 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-b814a09\" data-id=\"b814a09\" 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-aebd61c elementor-widget elementor-widget-progress\" data-id=\"aebd61c\" 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-aebd61c\">\n\t\t\t\tDifficulty\t\t\t<\/span>\n\t\t\n\t\t<div aria-labelledby=\"elementor-progress-bar-aebd61c\" 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-436c7815 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"436c7815\" 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-5e0e6d99\" data-id=\"5e0e6d99\" 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-1f84f110 elementor-widget elementor-widget-text-editor\" data-id=\"1f84f110\" 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\/non-deterministic-finite-automaton\/#Automate-fini-non-deterministe\" >Non-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\/non-deterministic-finite-automaton\/#Non-determinisme-et-mots-reconnus\" >Non-determinism and recognized words<\/a><\/li><\/ul><\/nav><\/div>\n<h2><span class=\"ez-toc-section\" id=\"Automate-fini-non-deterministe\"><\/span>Non-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> non-deterministic finite, 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 non-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>Note that a deterministic automaton is a particular case of a non-deterministic automaton which associates with any element of Q \u00d7 Vt a part of Q having zero or one element (exactly one if it is a complete automaton). We can say of a deterministic automaton that it is incomplete if it can be blocked, that is to say if there exists a state q and a letter a such that T (q, a) = \u2205. If it is complete, we have the following property:<\/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 non-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 (not always unique) state q &#039;\u2208 Q such that q (u) \u2192 Aq&#039;.<\/p>\n<\/div>\n<p><\/p>\n<p>The non-deterministic has however an essential consequence: there can be several derivations resulting from the initial state i which read a given word w, some of which can be blocked and others not, and in the latter case some can end in state accepting and others not. Acceptance takes place if there is at least one successful calculation. If all the calculations fail, there will be no other way to find out than to explore them all before knowing that the word w is not matched. The correct notion is therefore not that of calculation, but of a calculation tree associated with a word read by the automaton:<\/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>Given a non-deterministic finite automaton A, the derivation tree with root q \u2208 Q generated by reading the word u is a <a href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-2\/trees-and-trees\/\">tree<\/a> doubly labeled defined by induction on u:<br \/>If u = \u03b5, then the tree is reduced to its root q;<br \/>If u = av, the root q has outgoing transitions labeled by a \u2208 Vt to different computational trees generated by the reading of v and whose roots are labeled by the states of T (q, a).<\/p>\n<\/div>\n<p><\/p>\n<p>A derivation tree is constructed as in the case of a deterministic automaton. In the case of a non-deterministic finite automaton, it is not linear and can present various branches which will give various derivations leading or not to the recognition of the word.<\/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 word u is recognized by a non-deterministic automaton A iff one of the leaves of its calculation tree is labeled by an accepting state.<\/p>\n<\/div>\n<p><\/p>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Non-determinisme-et-mots-reconnus\"><\/span>Non-determinism and recognized words<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\n<p>We consider the following non-deterministic finite automaton A = ({a, b}, {1, 2, 3}, \u2206, {1}, {1}):<\/p>\n<p><\/p>\n<div>\n<figure><img decoding=\"async\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/05\/langage7.png\" alt=\"non-deterministic finite automaton\" width=\"263\" height=\"171\" title=\"\"><\/figure>\n<\/div>\n<p><\/p>\n<p>Is the word baabab accepted by automaton A?<\/p>\n<p><\/p>\n<div>\n<figure><img decoding=\"async\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/05\/langage8.png\" alt=\"non-deterministic finite automaton\" width=\"143\" height=\"260\" title=\"\"><\/figure>\n<\/div>\n<p><\/p>\n<p>No leaf corresponds to a final state, note that all the leaves end up in the well.<\/p>\n<p><\/p>\n<p>Like the deterministic automaton, it is possible to construct the words recognized by the automaton by looking at the input lines and output columns. The words of lengths n are then constructed by raising the transition matrix to the power of n.<\/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 Wiki home page Difficulty Easy 25% Non-deterministic finite automaton We usually draw a non-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-6358","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/6358","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=6358"}],"version-history":[{"count":3,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/6358\/revisions"}],"predecessor-version":[{"id":18589,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/6358\/revisions\/18589"}],"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=6358"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}