{"id":6365,"date":"2018-05-31T09:20:48","date_gmt":"2018-05-31T08:20:48","guid":{"rendered":"http:\/\/smart--grid.net\/?page_id=6365"},"modified":"2022-12-03T23:00:31","modified_gmt":"2022-12-03T22:00:31","slug":"determinisation-afi-vers-afd","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/en\/language-theory\/determinization-afi-vers-afd\/","title":{"rendered":"AFI to AFD determination"},"content":{"rendered":"<div data-elementor-type=\"wp-page\" data-elementor-id=\"6365\" class=\"elementor elementor-6365\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-a392f04 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"a392f04\" 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-7019ae2\" data-id=\"7019ae2\" 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-89d83e9 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"89d83e9\" 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-0eaf4bd\" data-id=\"0eaf4bd\" 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-84a36eb elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"84a36eb\" 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-a66d4a3\" data-id=\"a66d4a3\" 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-c1712d7 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"c1712d7\" 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-0a4e691 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"0a4e691\" 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-47068cf\" data-id=\"47068cf\" 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-c4c485c elementor-widget elementor-widget-progress\" data-id=\"c4c485c\" 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-c4c485c\">\n\t\t\t\tDifficulty\t\t\t<\/span>\n\t\t\n\t\t<div aria-labelledby=\"elementor-progress-bar-c4c485c\" 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-447dcbc8 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"447dcbc8\" 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-2b959913\" data-id=\"2b959913\" 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-7b8778cc elementor-widget elementor-widget-text-editor\" data-id=\"7b8778cc\" 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-afi-vers-afd\/#AFI-vers-AFD\" >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-afi-vers-afd\/#Autre-exemple\" >Another example<\/a><\/li><\/ul><\/nav><\/div>\n<h2><span class=\"ez-toc-section\" id=\"AFI-vers-AFD\"><\/span>AFI to AFD<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>The Rabin-Scott theorem says that any language recognized by a <a href=\"https:\/\/complex-systems-ai.com\/en\/language-theory\/\">automaton<\/a> indeterministic finite can be recognized by a <a href=\"https:\/\/complex-systems-ai.com\/en\/language-theory\/deterministic-finite-automaton\/\">deterministic finite automaton<\/a> (<a href=\"https:\/\/complex-systems-ai.com\/en\/language-theory\/determinization-e-afi-vers-afd\/\">determination<\/a> AFI to AFD). It is therefore possible to represent an indeterministic automaton by a deterministic automaton, this process is called determinization.<\/p>\n<p><\/p>\n<p><\/p>\n<p>Consider for example the<a href=\"https:\/\/complex-systems-ai.com\/en\/language-theory\/non-deterministic-finite-automaton\/\">non-deterministic finite automaton<\/a> (K, T, M, I, F) following:<br \/>K = {S1, S2, S3, S4}<br \/>T = {a, b, c}<br \/>M = {(S1, a, S1), (S1, a, S3), (S2, b, S2), (S2, b, S3), (S3, c, S3), (S3, c, S4) }<br \/>I = {S1, S2}<br \/>F = {S4}<br \/>corresponding to <a href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-2\/\">graph<\/a> next :<\/p>\n<p><\/p>\n<p><\/p>\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img fetchpriority=\"high\" decoding=\"async\" class=\"alignnone wp-image-6361\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/05\/langage9.png\" alt=\"AFI to AFD\" width=\"572\" height=\"285\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/05\/langage9.png 572w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/05\/langage9-300x149.png 300w\" sizes=\"(max-width: 572px) 100vw, 572px\" \/><\/figure>\n<\/div>\n<p><\/p>\n<p><\/p>\n<p>We then construct the states of the deterministic finite automaton (AFD) and their transition function. At the start, it has a single state which is composed of the set of initial states of the indeterministic finite automaton (AFI): in our example, the initial state of AFD is {S1, S2}.<\/p>\n<p><\/p>\n<p><\/p>\n<p>Each time we add a new state in the AFD, we determine its transition function by making the union of the corresponding lines in the transition table of<br \/>AFI: on our example, for the state {S1, S2}, we make the union of the lines corresponding to S1 and S2, and we determine the transition function<\/p>\n<p><\/p>\n<p><\/p>\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img decoding=\"async\" class=\"alignnone wp-image-6362\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/05\/langage10.png\" alt=\"AFI to AFD\" width=\"342\" height=\"82\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/05\/langage10.png 342w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/05\/langage10-300x72.png 300w\" sizes=\"(max-width: 342px) 100vw, 342px\" \/><\/figure>\n<\/div>\n<p><\/p>\n<p><\/p>\n<p>In other words, when we are in state \u201cS1 or S2 \u2033 and we read an a, we go to state\u201c S1 or S3 \u2033 (M ({S1, S2}, a) = {S1, S3 }), when we are in state \u201cS1 or S2 \u2033 and read a b, we go to state\u201c S2 or S3 \u2033 (M ({S1, S2}, b) = {S2, S3 }) and when we are in state \u201cS1 or S2 \u2033 and read a c, we go to the\u201c empty \u201dstate, corresponding to the error state (M ({S1, S2}, c) = \u2205.<\/p>\n<p><\/p>\n<p><\/p>\n<p>The states {S1, S3} and {S2, S3} are then added to the AFD and their transition function is determined according to the same principle. Gradually, we build the following transition table for AFD:<\/p>\n<p><\/p>\n<p><\/p>\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img decoding=\"async\" class=\"alignnone wp-image-6363\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/05\/langage11.png\" alt=\"AFI to AFD\" width=\"384\" height=\"141\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/05\/langage11.png 384w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/05\/langage11-300x110.png 300w\" sizes=\"(max-width: 384px) 100vw, 384px\" \/><\/figure>\n<\/div>\n<p><\/p>\n<p><\/p>\n<p>The set of AFD states is K &#039;= {{S1, S2}, {S1, S3}, {S2, S3}, {S3, S4}}. AFD states containing an AFI end state are end states. Here, AFI has a single final state S4 and the set of AFD final states is F &#039;= {{S3, S4}}. This AFD corresponds to the following graph:<\/p>\n<p><\/p>\n<p><\/p>\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-6364\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/05\/langage12.png\" alt=\"AFI to AFD\" width=\"342\" height=\"241\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/05\/langage12.png 342w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/05\/langage12-300x211.png 300w\" sizes=\"(max-width: 342px) 100vw, 342px\" \/><\/figure>\n<\/div>\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>Here is another example of AFI to AFD determinization.<\/p>\n<p><\/p>\n<p><\/p>\n<figure class=\"wp-block-image\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-6621\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/09\/langage53.png\" alt=\"AFI to AFD\" width=\"330\" height=\"67\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/09\/langage53.png 330w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/09\/langage53-300x61.png 300w\" sizes=\"(max-width: 330px) 100vw, 330px\" \/><\/figure>\n<p><\/p>\n<p><\/p>\n<p>In practice, we only construct the states accessible from I, step by step: we start from the initial state I, then we calculate all the transitions that start from I, then we start again with the new states obtained, etc.<\/p>\n<p><\/p>\n<p><\/p>\n<p>NB: the course method is also valid for the tutorials and the project. You use the one you understand best! You have the same example with the course notations after this method.<\/p>\n<p><\/p>\n<p><\/p>\n<p>initial state: I = {1} transition by a: {1, 2} transition by b: {1}. We just did {1} so we&#039;re going to do {1,2}<\/p>\n<p><\/p>\n<p><\/p>\n<p>state {1, 2} transition by a: {1, 2} transition by b: {1, 3}, we now do {1,3}<\/p>\n<p><\/p>\n<p><\/p>\n<p>state {1, 3} transition by a: {1, 2} transition by b: {1}. There are no unvisited states left. Only state {1,3} contains a terminal state, {1,3} is therefore terminal.<\/p>\n<p><\/p>\n<p><\/p>\n<p>Which gives us the following DFA:<\/p>\n<p><\/p>\n<p><\/p>\n<figure class=\"wp-block-image\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-6622\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/09\/langage54.png\" alt=\"AFI to AFD\" width=\"327\" height=\"118\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/09\/langage54.png 327w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/09\/langage54-300x108.png 300w\" sizes=\"(max-width: 327px) 100vw, 327px\" \/><\/figure>\n<p><\/p>\n<p><\/p>\n<p>The calculation by tables is much more readable.<\/p>\n<p><\/p>\n<p><\/p>\n<figure class=\"wp-block-table\">\n<table>\n<tbody>\n<tr>\n<td>delta<\/td>\n<td>To<\/td>\n<td>b<\/td>\n<\/tr>\n<tr>\n<td>1<\/td>\n<td>{1,2}<\/td>\n<td>{1}<\/td>\n<\/tr>\n<tr>\n<td>2<\/td>\n<td>\u2013<\/td>\n<td>{3}<\/td>\n<\/tr>\n<tr>\n<td>3<\/td>\n<td>\u2013<\/td>\n<td>\u2013<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/figure>\n<p><\/p>\n<p><\/p>\n<p>Let&#039;s calculate the delta prime states:<\/p>\n<p><\/p>\n<p><\/p>\n<figure class=\"wp-block-table\">\n<table>\n<tbody>\n<tr>\n<td>Detla prime<\/td>\n<td>To<\/td>\n<td>b<\/td>\n<\/tr>\n<tr>\n<td>1<\/td>\n<td>{1,2}<\/td>\n<td>1<\/td>\n<\/tr>\n<tr>\n<td>1,2<\/td>\n<td>{1,2}<\/td>\n<td>{1,3}<\/td>\n<\/tr>\n<tr>\n<td>{1,3}<\/td>\n<td>{1,2}<\/td>\n<td>{1}<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/figure>\n<p><\/p>\n<p><\/p>\n<p>The second line creates the state {1,3} for us. We notice that at the end, the automaton is the same as the one calculated with the previous method (state 3 is not useful since no one calls it).<\/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 Difficulty Easy 25% AFI to AFD The Rabin-Scott theorem says that any language recognized by a finite automaton \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-6365","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/6365","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=6365"}],"version-history":[{"count":7,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/6365\/revisions"}],"predecessor-version":[{"id":18595,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/6365\/revisions\/18595"}],"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=6365"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}