{"id":6380,"date":"2018-05-31T13:58:28","date_gmt":"2018-05-31T12:58:28","guid":{"rendered":"http:\/\/smart--grid.net\/?page_id=6380"},"modified":"2022-12-03T23:00:33","modified_gmt":"2022-12-03T22:00:33","slug":"determinisation-e-afi-vers-afd","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/en\/language-theory\/determinization-e-afi-vers-afd\/","title":{"rendered":"E-AFI to AFD determination"},"content":{"rendered":"<div data-elementor-type=\"wp-page\" data-elementor-id=\"6380\" class=\"elementor elementor-6380\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-38680ed elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"38680ed\" 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-ec1b4fe\" data-id=\"ec1b4fe\" 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-435a7d0 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"435a7d0\" 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-4cd7b57\" data-id=\"4cd7b57\" 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-c232b36 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"c232b36\" 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-228a2db\" data-id=\"228a2db\" 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-0238013 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"0238013\" 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\/Construction_par_sous-ensembles\" 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-1d06615 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"1d06615\" 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-ede4df1\" data-id=\"ede4df1\" 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-05fff81 elementor-widget elementor-widget-progress\" data-id=\"05fff81\" 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-05fff81\">\n\t\t\t\tDifficulty\t\t\t<\/span>\n\t\t\n\t\t<div aria-labelledby=\"elementor-progress-bar-05fff81\" 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-70e7d785 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"70e7d785\" 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-66879f5d\" data-id=\"66879f5d\" 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-6c5b59f6 elementor-widget elementor-widget-text-editor\" data-id=\"6c5b59f6\" 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\/determinization-e-afi-vers-afd\/#e-AFI-vers-AFD\" >e-AFI to 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\/determinization-e-afi-vers-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\/determinization-e-afi-vers-afd\/#Autre-exemple\" >Another example<\/a><\/li><\/ul><\/nav><\/div>\n<h2><span class=\"ez-toc-section\" id=\"e-AFI-vers-AFD\"><\/span>e-AFI to AFD<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>We now want to show that the language recognized by a <a href=\"https:\/\/complex-systems-ai.com\/en\/language-theory\/\">automaton<\/a> with empty transitions can also be done by a non-deterministic automaton without empty transitions (determination e-AFI towards <a href=\"https:\/\/complex-systems-ai.com\/en\/language-theory\/deterministic-finite-automaton\/\">AFD<\/a>). This operation will require the addition of new transitions in the automaton.<\/p>\n<p><\/p>\n<p><\/p>\n<p>Any language recognized by a <a href=\"https:\/\/complex-systems-ai.com\/en\/language-theory\/non-deterministic-finite-automaton\/\">AFN<\/a> with \u03b5\u2013transitions can be recognized by an AFN (without \u03b5\u2013transitions) having the same number of states.<\/p>\n<p><\/p>\n<p><\/p>\n<p>Construction of the AFN equivalent to an automaton with \u03b5 \u2013 transitions, by prolonging \u03b4 in \u03b41 (the transitive closure is all the states which can be reached by a state by a given transition).<\/p>\n<p><strong>First step: Addition of \u03b5 \u2013 transitions by transitive closure.<\/strong><\/p>\n<p><\/p>\n<p><\/p>\n<p>For all the states q accessible from p by \u03b5-transition (in several steps), we add a direct \u03b5 \u2013 transition from p to q. We thus extend the function \u03b4: \u03b41 (p, \u03b5) = all the states accessible from p by \u03b5 \u2013 transition.<\/p>\n<p><\/p>\n<p><\/p>\n<p><strong>Second step: Addition of additional transitions and additional initial states, then removal of \u03b5-transitions.<\/strong><\/p>\n<p><\/p>\n<p><\/p>\n<p>The initial states are all the states accessible from the initial states by \u03b5 \u2013 transition.<\/p>\n<p><\/p>\n<p><\/p>\n<p>For any transition from p to q by a letter, we add transitions from p to r with the same letter for all \u03b5 \u2013 transitions from q to r: \u03b41 (p, a) = \u03b4 (p, a) \u222a (\u222a<sub>q\u2208\u03b4 (p, a)<\/sub> \u03b41 (q, \u03b5)).<\/p>\n<p><\/p>\n<p><\/p>\n<p>We remove all \u03b5 \u2013 transitions<\/p>\n<p><\/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 e-AFI to AFD determinization.<\/div>\n<p><\/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<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=\"e-AFI to AFD\" width=\"400\" height=\"171\" title=\"\"><\/figure>\n<\/div>\n<p><\/p>\n<p><\/p>\n<p>There are two paths of length 1 which start with the transition on epsilon:<\/p>\n<p><\/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><\/p>\n<p>We add to the automaton two new transitions which summarize these two paths:<\/p>\n<p><\/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><\/p>\n<p>And we remove the transition (1, \u03b5, 3).<\/p>\n<p><\/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=\"e-AFI to AFD\" width=\"373\" height=\"220\" title=\"\"><\/figure>\n<\/div>\n<p><\/p>\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>\n<p><\/p>\n<p>The use of epsilon-transitions sometimes makes it possible to describe a language more clearly. It also makes it possible to simplify the description of certain operations (for example the union or the concatenation -&gt; see automaton of <a href=\"https:\/\/complex-systems-ai.com\/en\/language-theory\/construction-of-thompson\/\">Thompson<\/a>).<\/p>\n<p><\/p>\n<p><\/p>\n<p>The existence of epsilon-transitions makes the automaton non-deterministic since we always have the possibility of borrowing such a transition even when there is an ordinary transition that we could borrow.<\/p>\n<p><\/p>\n<p><\/p>\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<p><\/p>\n<p><\/p>\n<p>Consider the following automaton:<\/p>\n<p><\/p>\n<p><\/p>\n<figure><img decoding=\"async\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/09\/langage55.png\" alt=\"e-AFI to AFD\" width=\"241\" height=\"90\" title=\"\"><\/figure>\n<p><\/p>\n<p><\/p>\n<p>For this, it is first necessary to calculate, for each state, the \u03b5-successors of each state p, that is to say the set of states q such that there exists a path formed only of \u03b5-transitions starting from from p arriving in q.<\/p>\n<p><\/p>\n<p><\/p>\n<p>We calculate the \u03b5-successors of each state: Succ\u03b5 (p) = {q, r}, Succ\u03b5 (q) = {r}, Succ\u03b5 (r) = \u2205.<\/p>\n<p><\/p>\n<p><\/p>\n<p>We obtain the following NFA:<\/p>\n<p><\/p>\n<p><\/p>\n<figure><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/09\/langage56.png\" alt=\"e-AFI to AFD\" width=\"244\" height=\"98\" title=\"\"><\/figure>\n<p><\/p>\n<p><\/p>\n<p>You can then determine it with the NFA to DFA method, or you can determine it directly in its form with espilon transition like the following example.<\/p>\n<p><\/p>\n<p><\/p>\n<p>Let&#039;s take the automaton and transform it into a DFA:<\/p>\n<p><\/p>\n<p><\/p>\n<figure><img decoding=\"async\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/09\/langage55.png\" alt=\"e-AFI to AFD\" width=\"241\" height=\"90\" title=\"\"><\/figure>\n<p><\/p>\n<p><\/p>\n<p>The first step consists in calculating the epsilon-closing for each state of this automaton:<\/p>\n<p><\/p>\n<p><\/p>\n<figure>\n<table>\n<tbody>\n<tr>\n<td>Delta (Q)<\/td>\n<td>To<\/td>\n<td>b<\/td>\n<td>Closure -&gt; Q &#039;<\/td>\n<\/tr>\n<tr>\n<td>p<\/td>\n<td>p<\/td>\n<td>\u2013<\/td>\n<td>{p, q, r}<\/td>\n<\/tr>\n<tr>\n<td>q<\/td>\n<td>\u2013<\/td>\n<td>q<\/td>\n<td>{q, r}<\/td>\n<\/tr>\n<tr>\n<td>r<\/td>\n<td>r<\/td>\n<td>\u2013<\/td>\n<td>{r}<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/figure>\n<p><\/p>\n<p><\/p>\n<p>For each state of the closure, we calculate its transitions in the alphabet without epsilon:<\/p>\n<p><\/p>\n<p><\/p>\n<figure>\n<table>\n<tbody>\n<tr>\n<td>Delta (Q &#039;)<\/td>\n<td>To<\/td>\n<td>b<\/td>\n<\/tr>\n<tr>\n<td>{p, q, r}<\/td>\n<td>{p, r}<\/td>\n<td>{q}<\/td>\n<\/tr>\n<tr>\n<td>{q, r}<\/td>\n<td>{r}<\/td>\n<td>{q}<\/td>\n<\/tr>\n<tr>\n<td>{r}<\/td>\n<td>{r}<\/td>\n<td>\u2013<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/figure>\n<p><\/p>\n<p><\/p>\n<p>For each state obtained by the transitions, we calculate the closure:<\/p>\n<p><\/p>\n<p><\/p>\n<figure>\n<table>\n<tbody>\n<tr>\n<td>Delta (Q &#039;)<\/td>\n<td>To<\/td>\n<td>b<\/td>\n<\/tr>\n<tr>\n<td>{p, q, r}<\/td>\n<td>{p, r} -&gt; {p, q, r}<\/td>\n<td>{q} -&gt; {q, r}<\/td>\n<\/tr>\n<tr>\n<td>{q, r}<\/td>\n<td>{r} -&gt; {r}<\/td>\n<td>{q} -&gt; {q, r}<\/td>\n<\/tr>\n<tr>\n<td>{r}<\/td>\n<td>{r} -&gt; {r}<\/td>\n<td>\u2013<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/figure>\n<p><\/p>\n<p><\/p>\n<p>Denote by {p, q, r} = P; {q, r} = Q and {r} = R. We obtain the following automaton:<\/p>\n<p><\/p>\n<p><\/p>\n<figure><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/09\/langage58.png\" alt=\"e-AFI to AFD\" width=\"286\" height=\"84\" title=\"\"><\/figure>\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 Medium 50% e-AFI to AFD We now want to show that the language recognized by an automaton with transitions\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-6380","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/6380","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=6380"}],"version-history":[{"count":6,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/6380\/revisions"}],"predecessor-version":[{"id":18602,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/6380\/revisions\/18602"}],"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=6380"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}