{"id":6400,"date":"2018-06-04T10:00:35","date_gmt":"2018-06-04T09:00:35","guid":{"rendered":"http:\/\/smart--grid.net\/?page_id=6400"},"modified":"2022-12-03T23:00:40","modified_gmt":"2022-12-03T22:00:40","slug":"minimisation-dun-afd","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/en\/language-theory\/minimization-dun-afd\/","title":{"rendered":"Minimization of AFD"},"content":{"rendered":"<div data-elementor-type=\"wp-page\" data-elementor-id=\"6400\" class=\"elementor elementor-6400\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-2b7cf9e elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"2b7cf9e\" 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-fdde60b\" data-id=\"fdde60b\" 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-550777a elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"550777a\" 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-b2f481e\" data-id=\"b2f481e\" 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-938f948 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"938f948\" 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-d55b34f\" data-id=\"d55b34f\" 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-a32342e elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"a32342e\" 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\/Minimisation_d%27un_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-8744384 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"8744384\" 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-36bcd2d\" data-id=\"36bcd2d\" 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-579c1ac elementor-widget elementor-widget-progress\" data-id=\"579c1ac\" 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-579c1ac\">\n\t\t\t\tDifficulty\t\t\t<\/span>\n\t\t\n\t\t<div aria-labelledby=\"elementor-progress-bar-579c1ac\" 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-5cdda007 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"5cdda007\" 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-57dff5ed\" data-id=\"57dff5ed\" 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-77c5d911 elementor-widget elementor-widget-text-editor\" data-id=\"77c5d911\" 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\/minimization-dun-afd\/#Minimisation-dun-AFD\" >Minimization of AFD<\/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\/minimization-dun-afd\/#Exemple\" >Example<\/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\/minimization-dun-afd\/#Autre-exemple\" >Another example<\/a><\/li><\/ul><\/nav><\/div>\n<h2><span class=\"ez-toc-section\" id=\"Minimisation-dun-AFD\"><\/span>Minimization of AFD<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>Myhill-Nerode theorem (minimization of a <a href=\"https:\/\/complex-systems-ai.com\/en\/language-theory\/deterministic-finite-automaton\/\">AFD<\/a>). Let L be a rational language. Among all L-recognizing AFDs, there is one and only one that has a minimal number of states.<\/p>\n<p>Before minimizing an AFD, it must be completed, ie add a trash state like the state R on the diagram below.<\/p>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img fetchpriority=\"high\" decoding=\"async\" class=\"alignnone wp-image-6401\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/05\/langage22.png\" alt=\"minimization of an AFD\" width=\"416\" height=\"237\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/05\/langage22.png 416w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/05\/langage22-300x171.png 300w\" sizes=\"(max-width: 416px) 100vw, 416px\" \/><\/figure>\n<\/div>\n\n<p>The minimization algorithm is as follows:<\/p>\n\n<ol class=\"wp-block-list\">\n<li>Complete the AFD named D<\/li>\n<li>Construct an initial partition \u220f containing two sets I and II of states such that \u220f = {I = (terminal acceptance states of D), II = (other states of D)}<\/li>\n<li>For each state of D do\n<ol>\n<li>Build the transition table<\/li>\n<li>Mark the states of departure and arrival according to their group of \u220f<\/li>\n<\/ol>\n<\/li>\n<li>If states of the same group of \u220f have divergent behaviors\n<ol>\n<li>Separate the states into a new group (III for example) - preferably do only one separation per iteration.<\/li>\n<li>Return to 3<\/li>\n<\/ol>\n<\/li>\n<li>End: the new states are the groups of \u220f<\/li>\n<\/ol>\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Exemple\"><\/span>Example<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n<p>Let us take the example of AFD above. It is indeed deterministic as shown by the transition table.<\/p>\n\n<p>Let&#039;s look at the transition table in step 3:<\/p>\n\n<figure class=\"wp-block-table\">\n<table>\n<tbody>\n<tr>\n<td>\u00a0<\/td>\n<td>To<\/td>\n<td>b<\/td>\n<td>vs<\/td>\n<\/tr>\n<tr>\n<td>0 (I)<\/td>\n<td>2 (II)<\/td>\n<td>5 (II)<\/td>\n<td>R (I)<\/td>\n<\/tr>\n<tr>\n<td>2 (II)<\/td>\n<td>R (I)<\/td>\n<td>R (I)<\/td>\n<td>R (I)<\/td>\n<\/tr>\n<tr>\n<td>5 (II)<\/td>\n<td>R (I)<\/td>\n<td>R (I)<\/td>\n<td>8 (II)<\/td>\n<\/tr>\n<tr>\n<td>8 (II)<\/td>\n<td>R (I)<\/td>\n<td>R (I)<\/td>\n<td>8 (II)<\/td>\n<\/tr>\n<tr>\n<td>R (I)<\/td>\n<td>R (I)<\/td>\n<td>R (I)<\/td>\n<td>R (I)<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/figure>\n\n<p>We notice when in group I, the behavior of O and R diverge, we will therefore separate them into two groups: I = (0) and III = (R)<\/p>\n\n<p>Here is the new transition table:<\/p>\n\n<figure class=\"wp-block-table\">\n<table>\n<tbody>\n<tr>\n<td>\u00a0<\/td>\n<td>To<\/td>\n<td>b<\/td>\n<td>vs<\/td>\n<\/tr>\n<tr>\n<td>0 (I)<\/td>\n<td>2 (II)<\/td>\n<td>5 (II)<\/td>\n<td>R (III)<\/td>\n<\/tr>\n<tr>\n<td>2 (II)<\/td>\n<td>R (III)<\/td>\n<td>R (III)<\/td>\n<td>R (III)<\/td>\n<\/tr>\n<tr>\n<td>5 (II)<\/td>\n<td>R (III)<\/td>\n<td>R (III)<\/td>\n<td>8 (II)<\/td>\n<\/tr>\n<tr>\n<td>8 (II)<\/td>\n<td>R (III)<\/td>\n<td>R (III)<\/td>\n<td>8 (II)<\/td>\n<\/tr>\n<tr>\n<td>R (III)<\/td>\n<td>R (III)<\/td>\n<td>R (III)<\/td>\n<td>R (III)<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/figure>\n\n<p>We notice when in group II, the behavior of 2 and 5, 8 diverge, we will therefore separate them into two groups: II = (5, 8) and IV = (2)<\/p>\n\n<p>Here is the new transition table:<\/p>\n\n<figure class=\"wp-block-table\">\n<table>\n<tbody>\n<tr>\n<td>\u00a0<\/td>\n<td>To<\/td>\n<td>b<\/td>\n<td>vs<\/td>\n<\/tr>\n<tr>\n<td>0 (I)<\/td>\n<td>2 (IV)<\/td>\n<td>5 (II)<\/td>\n<td>R (III)<\/td>\n<\/tr>\n<tr>\n<td>2 (IV)<\/td>\n<td>R (III)<\/td>\n<td>R (III)<\/td>\n<td>R (III)<\/td>\n<\/tr>\n<tr>\n<td>5 (II)<\/td>\n<td>R (III)<\/td>\n<td>R (III)<\/td>\n<td>8 (II)<\/td>\n<\/tr>\n<tr>\n<td>8 (II)<\/td>\n<td>R (III)<\/td>\n<td>R (III)<\/td>\n<td>8 (II)<\/td>\n<\/tr>\n<tr>\n<td>R (III)<\/td>\n<td>R (III)<\/td>\n<td>R (III)<\/td>\n<td>R (III)<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/figure>\n\n<p>We no longer observe any divergence between the groups, so we can perform the transition table with minimized AFD giving the following transition table:<\/p>\n\n<figure class=\"wp-block-table\">\n<table>\n<tbody>\n<tr>\n<td>\u00a0<\/td>\n<td>To<\/td>\n<td>b<\/td>\n<td>vs<\/td>\n<\/tr>\n<tr>\n<td>I<\/td>\n<td>IV<\/td>\n<td>II<\/td>\n<td>III<\/td>\n<\/tr>\n<tr>\n<td>IV<\/td>\n<td>III<\/td>\n<td>III<\/td>\n<td>III<\/td>\n<\/tr>\n<tr>\n<td>II<\/td>\n<td>III<\/td>\n<td>III<\/td>\n<td>II<\/td>\n<\/tr>\n<tr>\n<td>III<\/td>\n<td>III<\/td>\n<td>III<\/td>\n<td>III<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/figure>\n\n<p>The initial state is I (in relation to its equivalent in D), and the terminal states of the automaton are II and IV (in relation to their equivalents in D).<\/p>\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Autre-exemple\"><\/span>Another example<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n<p>Consider the following automaton:<\/p>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img decoding=\"async\" class=\"alignnone wp-image-6637\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/09\/langage59.gif\" alt=\"minimization of an AFD\" width=\"283\" height=\"283\" title=\"\"><\/figure>\n<\/div>\n\n<p>The initialization phase makes it possible to obtain the non-terminal group I and the terminal group II:<\/p>\n\n<figure class=\"wp-block-table\">\n<table>\n<tbody>\n<tr>\n<td>\u00a0<\/td>\n<td>TO<\/td>\n<td>B<\/td>\n<td>VS<\/td>\n<td>D<\/td>\n<\/tr>\n<tr>\n<td>Init<\/td>\n<td>I<\/td>\n<td>II<\/td>\n<td>I<\/td>\n<td>II<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/figure>\n\n<p>Let&#039;s look at the transitions for each state according to groups I and II:<\/p>\n\n<figure class=\"wp-block-table\">\n<table>\n<tbody>\n<tr>\n<td>Alphabet<\/td>\n<td>TO<\/td>\n<td>B<\/td>\n<td>VS<\/td>\n<td>D<\/td>\n<\/tr>\n<tr>\n<td>To<\/td>\n<td>II<\/td>\n<td>II<\/td>\n<td>I<\/td>\n<td>II<\/td>\n<\/tr>\n<tr>\n<td>O<\/td>\n<td>I<\/td>\n<td>II<\/td>\n<td>I<\/td>\n<td>II<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/figure>\n\n<p>Then we perform the separation of sets. Two states are in the same set if they were already in the same set and if the transitions lead in the same sets. In this example, B and D behave in exactly the same way, so they stay together. On the other hand, A and C which were part of the same set behave differently on the symbol &quot;a&quot;. Consequently, the set noted I is divided into two. So we get:<\/p>\n\n<figure class=\"wp-block-table\">\n<table>\n<tbody>\n<tr>\n<td>\u00a0<\/td>\n<td>TO<\/td>\n<td>B<\/td>\n<td>VS<\/td>\n<td>D<\/td>\n<\/tr>\n<tr>\n<td>Init<\/td>\n<td>I<\/td>\n<td>II<\/td>\n<td>I<\/td>\n<td>II<\/td>\n<\/tr>\n<tr>\n<td>To<\/td>\n<td>II<\/td>\n<td>II<\/td>\n<td>I<\/td>\n<td>II<\/td>\n<\/tr>\n<tr>\n<td>0<\/td>\n<td>I<\/td>\n<td>II<\/td>\n<td>I<\/td>\n<td>II<\/td>\n<\/tr>\n<tr>\n<td>Separation 1<\/td>\n<td>I<\/td>\n<td>II<\/td>\n<td>III<\/td>\n<td>II<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/figure>\n\n<p>The current situation (the Balance sheet 1 line) is different than the starting situation. So we have to start over.<\/p>\n\n<figure class=\"wp-block-table\">\n<table>\n<tbody>\n<tr>\n<td>\u00a0<\/td>\n<td>TO<\/td>\n<td>B<\/td>\n<td>VS<\/td>\n<td>D<\/td>\n<\/tr>\n<tr>\n<td>Init<\/td>\n<td>I<\/td>\n<td>II<\/td>\n<td>I<\/td>\n<td>II<\/td>\n<\/tr>\n<tr>\n<td>To<\/td>\n<td>II<\/td>\n<td>II<\/td>\n<td>I<\/td>\n<td>II<\/td>\n<\/tr>\n<tr>\n<td>0<\/td>\n<td>I<\/td>\n<td>II<\/td>\n<td>I<\/td>\n<td>II<\/td>\n<\/tr>\n<tr>\n<td>Separation 1<\/td>\n<td>I<\/td>\n<td>II<\/td>\n<td>III<\/td>\n<td>II<\/td>\n<\/tr>\n<tr>\n<td>TO<\/td>\n<td>II<\/td>\n<td>II<\/td>\n<td>III<\/td>\n<td>II<\/td>\n<\/tr>\n<tr>\n<td>0<\/td>\n<td>III<\/td>\n<td>II<\/td>\n<td>III<\/td>\n<td>II<\/td>\n<\/tr>\n<tr>\n<td>Separation 2<\/td>\n<td>I<\/td>\n<td>II<\/td>\n<td>III<\/td>\n<td>II<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/figure>\n\n<p>The \u201cSeparation 2\u201d line is identical to the \u201cSeparation 1\u201d line. Consequently, in each of the remaining sets, the states are not distinguishable (they behave in exactly the same way and are therefore &quot;redundant&quot;).<\/p>\n\n<p>So we can build the new <a href=\"https:\/\/complex-systems-ai.com\/en\/language-theory\/\">automaton<\/a> by associating a state to each set. The transitions are indicated by the table. The initial state is the one containing the initial state of the starting automaton: here I contains state A, initial state. The final states are the states whose corresponding set contains at least one final state: here, II contains B and D which are final.<\/p>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img decoding=\"async\" class=\"alignnone wp-image-6638\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/09\/langage60.gif\" alt=\"minimization of an AFD\" width=\"283\" height=\"283\" title=\"\"><\/figure>\n<\/div>\n\n<p>So far, we have &quot;merged&quot; the indistinguishable states. You must now delete all the remaining unnecessary states. In our example, state III is a sterile state (non-terminal and without transition), therefore useless. It must therefore be deleted. Hence the minimal deterministic automaton of the following figure:<\/p>\n\n<figure class=\"wp-block-image\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-6639\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/09\/langage61.gif\" alt=\"minimization of an AFD\" width=\"283\" height=\"283\" title=\"\"><\/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 Wiki home page Difficulty Medium 50% Minimization of a DFA Myhill-N\u00e9rode theorem (minimization of a DFA). Let L be a rational language. Among all\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-6400","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/6400","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=6400"}],"version-history":[{"count":5,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/6400\/revisions"}],"predecessor-version":[{"id":18613,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/6400\/revisions\/18613"}],"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=6400"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}