{"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\/es\/teoria-del-lenguaje\/minimizacion-dun-afd\/","title":{"rendered":"Minimizaci\u00f3n de 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\/es\/teoria-del-lenguaje\/\">\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\">Teor\u00eda del lenguaje<\/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\/es\/\">\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\">Pagina de inicio<\/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\tDificultad\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\">Promedio<\/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\">Contenido<\/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=\"Tabla de contenido alternativo\"><span class=\"ez-toc-js-icon-con\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Palanca<\/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\/es\/teoria-del-lenguaje\/minimizacion-dun-afd\/#Minimisation-dun-AFD\" >Minimizaci\u00f3n de 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\/es\/teoria-del-lenguaje\/minimizacion-dun-afd\/#Exemple\" >Ejemplo<\/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\/es\/teoria-del-lenguaje\/minimizacion-dun-afd\/#Autre-exemple\" >Otro ejemplo<\/a><\/li><\/ul><\/nav><\/div>\n<h2><span class=\"ez-toc-section\" id=\"Minimisation-dun-AFD\"><\/span>Minimizaci\u00f3n de AFD<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>Teorema de Myhill-Nerode (minimizaci\u00f3n de un <a href=\"https:\/\/complex-systems-ai.com\/es\/teoria-del-lenguaje\/determinista-finito-automata\/\">AFD<\/a>). Sea L un lenguaje racional. Entre todos los AFD que reconocen L, hay uno y solo uno que tiene un n\u00famero m\u00ednimo de estados.<\/p>\n<p>Antes de minimizar un AFD, debe completarse, es decir, agregar un estado de basura como el estado R en el diagrama a continuaci\u00f3n.<\/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=\"minimizaci\u00f3n de una 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>El algoritmo de minimizaci\u00f3n es el siguiente:<\/p>\n\n<ol class=\"wp-block-list\">\n<li>Completa el AFD llamado D<\/li>\n<li>Construya una partici\u00f3n inicial \u220f que contenga dos conjuntos I y II de estados tales que \u220f = {I = (estados de aceptaci\u00f3n terminal de D), II = (otros estados de D)}<\/li>\n<li>Para cada estado de D hacer\n<ol>\n<li>Construye la mesa de transici\u00f3n<\/li>\n<li>Marque los estados de salida y llegada seg\u00fan su grupo de \u220f<\/li>\n<\/ol>\n<\/li>\n<li>Si los estados del mismo grupo de \u220f tienen comportamientos divergentes\n<ol>\n<li>Separe los estados en un nuevo grupo (III por ejemplo); preferiblemente haga solo una separaci\u00f3n por iteraci\u00f3n.<\/li>\n<li>Regresar a 3<\/li>\n<\/ol>\n<\/li>\n<li>Fin: los nuevos estados son los grupos de \u220f<\/li>\n<\/ol>\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Exemple\"><\/span>Ejemplo<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n<p>Tomemos el ejemplo de AFD anterior. De hecho, es determinista como se muestra en la tabla de transici\u00f3n.<\/p>\n\n<p>Veamos la tabla de transici\u00f3n en el paso 3:<\/p>\n\n<figure class=\"wp-block-table\">\n<table>\n<tbody>\n<tr>\n<td>\u00a0<\/td>\n<td>Para<\/td>\n<td>B<\/td>\n<td>vs<\/td>\n<\/tr>\n<tr>\n<td>0 (yo)<\/td>\n<td>2 (II)<\/td>\n<td>5 (II)<\/td>\n<td>R (yo)<\/td>\n<\/tr>\n<tr>\n<td>2 (II)<\/td>\n<td>R (yo)<\/td>\n<td>R (yo)<\/td>\n<td>R (yo)<\/td>\n<\/tr>\n<tr>\n<td>5 (II)<\/td>\n<td>R (yo)<\/td>\n<td>R (yo)<\/td>\n<td>8 (II)<\/td>\n<\/tr>\n<tr>\n<td>8 (II)<\/td>\n<td>R (yo)<\/td>\n<td>R (yo)<\/td>\n<td>8 (II)<\/td>\n<\/tr>\n<tr>\n<td>R (yo)<\/td>\n<td>R (yo)<\/td>\n<td>R (yo)<\/td>\n<td>R (yo)<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/figure>\n\n<p>Notamos cuando en el grupo I, el comportamiento de O y R divergen, por lo tanto los separaremos en dos grupos: I = (0) y III = (R)<\/p>\n\n<p>Aqu\u00ed est\u00e1 la nueva tabla de transici\u00f3n:<\/p>\n\n<figure class=\"wp-block-table\">\n<table>\n<tbody>\n<tr>\n<td>\u00a0<\/td>\n<td>Para<\/td>\n<td>B<\/td>\n<td>vs<\/td>\n<\/tr>\n<tr>\n<td>0 (yo)<\/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>Notamos que cuando en el grupo II, el comportamiento de 2 y 5, 8 divergen, los separaremos en dos grupos: II = (5, 8) y IV = (2)<\/p>\n\n<p>Aqu\u00ed est\u00e1 la nueva tabla de transici\u00f3n:<\/p>\n\n<figure class=\"wp-block-table\">\n<table>\n<tbody>\n<tr>\n<td>\u00a0<\/td>\n<td>Para<\/td>\n<td>B<\/td>\n<td>vs<\/td>\n<\/tr>\n<tr>\n<td>0 (yo)<\/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>Ya no observamos ninguna divergencia entre los grupos, por lo que podemos realizar la tabla de transici\u00f3n con AFD minimizado dando la siguiente tabla de transici\u00f3n:<\/p>\n\n<figure class=\"wp-block-table\">\n<table>\n<tbody>\n<tr>\n<td>\u00a0<\/td>\n<td>Para<\/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>El estado inicial es I (en relaci\u00f3n con su equivalente en D), y los estados terminales del aut\u00f3mata son II y IV (en relaci\u00f3n con sus equivalentes en D).<\/p>\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Autre-exemple\"><\/span>Otro ejemplo<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n<p>Considere el siguiente aut\u00f3mata:<\/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=\"minimizaci\u00f3n de una AFD\" width=\"283\" height=\"283\" title=\"\"><\/figure>\n<\/div>\n\n<p>La fase de inicializaci\u00f3n permite obtener el grupo no terminal I y el grupo terminal II:<\/p>\n\n<figure class=\"wp-block-table\">\n<table>\n<tbody>\n<tr>\n<td>\u00a0<\/td>\n<td>PARA<\/td>\n<td>B<\/td>\n<td>VS<\/td>\n<td>D<\/td>\n<\/tr>\n<tr>\n<td>En eso<\/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>Veamos las transiciones para cada estado seg\u00fan los grupos I y II:<\/p>\n\n<figure class=\"wp-block-table\">\n<table>\n<tbody>\n<tr>\n<td>Alfabeto<\/td>\n<td>PARA<\/td>\n<td>B<\/td>\n<td>VS<\/td>\n<td>D<\/td>\n<\/tr>\n<tr>\n<td>Para<\/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>Luego realizamos la separaci\u00f3n de conjuntos. Dos estados est\u00e1n en el mismo conjunto si ya estaban en el mismo conjunto y si las transiciones conducen a los mismos conjuntos. En este ejemplo, B y D se comportan exactamente de la misma manera, por lo que permanecen juntos. Por otro lado, A y C que formaban parte del mismo conjunto se comportan de manera diferente en el s\u00edmbolo &quot;a&quot;. En consecuencia, el conjunto anotado I se divide en dos. Entonces obtenemos:<\/p>\n\n<figure class=\"wp-block-table\">\n<table>\n<tbody>\n<tr>\n<td>\u00a0<\/td>\n<td>PARA<\/td>\n<td>B<\/td>\n<td>VS<\/td>\n<td>D<\/td>\n<\/tr>\n<tr>\n<td>En eso<\/td>\n<td>I<\/td>\n<td>II<\/td>\n<td>I<\/td>\n<td>II<\/td>\n<\/tr>\n<tr>\n<td>Para<\/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>Separaci\u00f3n 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>La situaci\u00f3n actual (la l\u00ednea del Balance 1) es diferente a la situaci\u00f3n inicial. Entonces tenemos que empezar de nuevo.<\/p>\n\n<figure class=\"wp-block-table\">\n<table>\n<tbody>\n<tr>\n<td>\u00a0<\/td>\n<td>PARA<\/td>\n<td>B<\/td>\n<td>VS<\/td>\n<td>D<\/td>\n<\/tr>\n<tr>\n<td>En eso<\/td>\n<td>I<\/td>\n<td>II<\/td>\n<td>I<\/td>\n<td>II<\/td>\n<\/tr>\n<tr>\n<td>Para<\/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>Separaci\u00f3n 1<\/td>\n<td>I<\/td>\n<td>II<\/td>\n<td>III<\/td>\n<td>II<\/td>\n<\/tr>\n<tr>\n<td>PARA<\/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>Separaci\u00f3n 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>La l\u00ednea &quot;Separaci\u00f3n 2&quot; es id\u00e9ntica a la l\u00ednea &quot;Separaci\u00f3n 1&quot;. En consecuencia, en cada uno de los conjuntos restantes, los estados no son distinguibles (se comportan exactamente de la misma manera y, por lo tanto, son &quot;redundantes&quot;).<\/p>\n\n<p>Para que podamos construir el nuevo <a href=\"https:\/\/complex-systems-ai.com\/es\/teoria-del-lenguaje\/\">aut\u00f3mata<\/a> asociando un estado a cada conjunto. Las transiciones se indican en la tabla. El estado inicial es el que contiene el estado inicial del aut\u00f3mata de partida: aqu\u00ed I contiene el estado A, estado inicial. Los estados finales son los estados cuyo conjunto correspondiente contiene al menos un estado final: aqu\u00ed, II contiene B y D que son finales.<\/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=\"minimizaci\u00f3n de una AFD\" width=\"283\" height=\"283\" title=\"\"><\/figure>\n<\/div>\n\n<p>Hasta ahora, hemos &quot;fusionado&quot; los estados indistinguibles. Ahora debe eliminar todos los estados innecesarios restantes. En nuestro ejemplo, el estado III es un estado est\u00e9ril (no terminal y sin transici\u00f3n), por lo tanto, in\u00fatil. Por tanto, debe suprimirse. De ah\u00ed el aut\u00f3mata determinista m\u00ednimo de la siguiente figura:<\/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=\"minimizaci\u00f3n de una 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>Teor\u00eda del lenguaje Wiki p\u00e1gina de inicio Dificultad Media 50% Minimizaci\u00f3n de un DFA Teorema de Myhill-N\u00e9rode (minimizaci\u00f3n de un DFA). Sea L un lenguaje racional. Entre todos\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\/es\/wp-json\/wp\/v2\/pages\/6400","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/comments?post=6400"}],"version-history":[{"count":5,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/6400\/revisions"}],"predecessor-version":[{"id":18613,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/6400\/revisions\/18613"}],"up":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/5028"}],"wp:attachment":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/media?parent=6400"}],"curies":[{"name":"gracias","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}