{"id":6515,"date":"2018-07-10T15:30:33","date_gmt":"2018-07-10T14:30:33","guid":{"rendered":"http:\/\/smart--grid.net\/?page_id=6515"},"modified":"2022-12-03T23:00:47","modified_gmt":"2022-12-03T22:00:47","slug":"algorithme-de-mcnaughton-et-yamada","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/en\/language-theory\/mcnaughton-and-yamada-algorithm\/","title":{"rendered":"McNaughton and Yamada algorithm"},"content":{"rendered":"<div data-elementor-type=\"wp-page\" data-elementor-id=\"6515\" class=\"elementor elementor-6515\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-50fed04 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"50fed04\" 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-032c4b9\" data-id=\"032c4b9\" 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-0552b81 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"0552b81\" 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-b581161\" data-id=\"b581161\" 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-42a1084 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"42a1084\" 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-8cc009a\" data-id=\"8cc009a\" 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-274d62d elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"274d62d\" 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:\/\/en.wikipedia.org\/wiki\/Kleene%27s_algorithm\" 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-e2c64e4 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"e2c64e4\" 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-362956e\" data-id=\"362956e\" 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-b1b1892 elementor-widget elementor-widget-progress\" data-id=\"b1b1892\" 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-b1b1892\">\n\t\t\t\tDifficulty\t\t\t<\/span>\n\t\t\n\t\t<div aria-labelledby=\"elementor-progress-bar-b1b1892\" 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-58515bda elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"58515bda\" 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-22669a59\" data-id=\"22669a59\" 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-43ea4386 elementor-widget elementor-widget-text-editor\" data-id=\"43ea4386\" 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\/mcnaughton-and-yamada-algorithm\/#Algorithme-de-McNaughton-et-Yamada\" >McNaughton and Yamada algorithm<\/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\/mcnaughton-and-yamada-algorithm\/#Exemple\" >Example<\/a><\/li><\/ul><\/nav><\/div>\n<h2><span class=\"ez-toc-section\" id=\"Algorithme-de-McNaughton-et-Yamada\"><\/span>McNaughton and Yamada algorithm<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>The algorithm of <a href=\"https:\/\/complex-systems-ai.com\/en\/language-theory\/brzozowski-and-mccluskey-algorithm\/\">McNaughton<\/a> and Yamada follows the next steps. Given a <a href=\"https:\/\/complex-systems-ai.com\/en\/language-theory\/\">automaton<\/a> To <i>not<\/i>\u00a0states, and whose states are numbered from 1 to\u00a0<i>not<\/i>, we give an expression for the languages composed of the words which label the paths of\u00a0<i>i<\/i>\u00a0To\u00a0<i>j<\/i>, for any couple\u00a0<i>i<\/i>,\u00a0<i>j<\/i>. This expression is built by induction using a condition on the paths. This condition states that the paths only pass through certain authorized states.<\/p>\n<p><\/p>\n<p>Our automaton having\u00a0<i>not<\/i>\u00a0states, so we focus on building a <a href=\"https:\/\/complex-systems-ai.com\/en\/language-theory\/regular-languages-and-regular-expressions\/\">regular expression<\/a> for each of\u00a0<i>not<\/i>\u00d7<i>not<\/i>\u00a0languages\u00a0<i>THE<sub>s, s&#039;<\/sub><\/i>\u00a0= {\u00a0<i>w<\/i>\u2208X * |\u00a0<i>s<\/i>.<i>w<\/i>\u00a0=\u00a0<i>s<\/i>&#039;} formed by all the words that send a state\u00a0<i>s<\/i>\u00a0any on another state\u00a0<i>s&#039;<\/i>. If we succeed, the language recognized by the automaton will be the value of a finite union of regular expressions and therefore of a regular expression.<\/p>\n<p><\/p>\n<p>The idea is to proceed step by step by taking into account an increasing number of intermediate states between\u00a0<i>s<\/i>\u00a0and\u00a0<i>s&#039;<\/i>. The states being assumed to be numbered from 0 to\u00a0<i>not<\/i>, we start with\u00a0<i>no<\/i>\u00a0intermediate state, then only\u00a0<i>s<sub>0<\/sub><\/i>, then\u00a0<i>s<sub>0<\/sub><\/i>\u00a0and\u00a0<i>s<sub>1<\/sub><\/i>, then\u00a0<i>s<sub>0<\/sub><\/i>,\u00a0<i>s<sub>1<\/sub><\/i>\u00a0and\u00a0<i>s<sub>2<\/sub><\/i>, etc.<\/p>\n<p><\/p>\n<p>We notice\u00a0<i>THE<sub>s, s&#039;<\/sub><sup>(k)<\/sup><\/i>\u00a0is the expression for the set of words which label paths from s to s&#039; and whose intermediate vertices are less than or equal to k. The starting vertices s and ending s&#039; are not intermediate, so they are not constrained to be less than or equal to k.<\/p>\n<p><\/p>\n<p>We build the <i>THE<sub>s, s&#039;<\/sub><sup>(k)<\/sup><\/i>\u00a0by induction on k, starting with k = 0, and ending with k = n. When k = n, the constraint on k is no longer a restriction, and <i>THE<sub>s, s&#039;<\/sub><sup>(k)<\/sup><\/i>=<i>THE<sub>s, s&#039;\u00a0<\/sub><\/i>\u00a0if s \u2260 s&#039;, and \u03b5 +<i>THE<sub>s, s<\/sub><sup>(not)<\/sup><\/i>=<i>THE<sub>s, s<\/sub><\/i>.<\/p>\n<p><\/p>\n<p>For k = 0, since the vertices are numbered starting from 1, the constraint simply expresses that there is no intermediate vertex. The only paths are transitions from s to s&#039; (we ignore a path of length 0 in state s).<\/p>\n<p><\/p>\n<p>We therefore have with s = p and s&#039; = q:<\/p>\n<p><\/p>\n<figure><img decoding=\"async\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/langage40.png\" alt=\"McNaughton and Yamada algorithm\" width=\"150\" height=\"80\" title=\"\"><\/figure>\n<p><\/p>\n<p>For induction, we consider a path from s to s&#039; whose intermediate vertices are smaller than k. Two cases are then possible:<\/p>\n<p><\/p>\n<ol class=\"wp-block-list\">\n<li>the intermediate vertices are smaller than k-1, then the label is in <i>THE<sub>s, s&#039;<\/sub><sup>(k-1)<\/sup><\/i><\/li>\n<li>the path goes through state k. We then decompose the path into parts whose intermediate vertices are smaller than k-1. For this, we consider each occurrence of the vertex k in this path: between two consecutive occurrences, the intermediate vertices are smaller than k-1. We then have the formula with s = p and s&#039; = q:\u00a0<img decoding=\"async\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/langage41.png\" alt=\"McNaughton and Yamada algorithm\" width=\"301\" height=\"45\" title=\"\">.<\/li>\n<\/ol>\n<p><\/p>\n<p>There are therefore n + 1 steps. Each of the steps requires the computation of n\u00b2 expressions, and the size of the expressions themselves increases with k.<\/p>\n<p><\/p>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Exemple\"><\/span>Example<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<div>Here is an example of McNaughton and Yamada&#039;s algorithm.<\/div>\n<p><\/p>\n<p>Consider the following automaton:<\/p>\n<p><\/p>\n<figure><img fetchpriority=\"high\" decoding=\"async\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/langage33.png\" alt=\"McNaughton and Yamada algorithm\" width=\"291\" height=\"214\" title=\"\"><\/figure>\n<p><\/p>\n<p>With k = 0 we have:<\/p>\n<p><\/p>\n<figure><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/langage42.png\" alt=\"McNaughton and Yamada algorithm\" width=\"299\" height=\"175\" title=\"\"><\/figure>\n<p><\/p>\n<p>Then k = 1:<\/p>\n<p><\/p>\n<figure><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/langage43.png\" alt=\"McNaughton and Yamada algorithm\" width=\"320\" height=\"311\" title=\"\"><\/figure>\n<p><\/p>\n<p>Then k = 2:<\/p>\n<p><\/p>\n<figure><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/langage44.png\" alt=\"McNaughton and Yamada algorithm\" width=\"311\" height=\"312\" title=\"\"><\/figure>\n<p><\/p>\n<p>Then k = 3:<\/p>\n<p><\/p>\n<figure><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/langage45.png\" alt=\"McNaughton and Yamada algorithm\" width=\"318\" height=\"307\" title=\"\"><\/figure>\n<p><\/p>\n<p>For the last step we just calculate the two expressions that interest us (initial states to final states):<\/p>\n<p><\/p>\n<figure><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/langage46.png\" alt=\"McNaughton and Yamada algorithm\" width=\"321\" height=\"45\" title=\"\"><\/figure>\n<p><\/p>\n<p>The desired expression is therefore ab (a + b) \u2217 + (b + aa) a \u2217.<\/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 Homepage Wiki Difficulty Medium 50% McNaughton and Yamada&#039;s algorithm McNaughton and Yamada&#039;s algorithm follows the following steps. Given \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-6515","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/6515","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=6515"}],"version-history":[{"count":9,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/6515\/revisions"}],"predecessor-version":[{"id":18634,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/6515\/revisions\/18634"}],"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=6515"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}