{"id":6545,"date":"2018-07-10T15:46:28","date_gmt":"2018-07-10T14:46:28","guid":{"rendered":"http:\/\/smart--grid.net\/?page_id=6545"},"modified":"2022-12-03T23:01:56","modified_gmt":"2022-12-03T22:01:56","slug":"algorithme-de-brzozowski-et-mccluskey","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/es\/teoria-del-lenguaje\/algoritmo-brzozowski-y-mccluskey\/","title":{"rendered":"Algoritmo de Brzozowski y McCluskey"},"content":{"rendered":"<div data-elementor-type=\"wp-page\" data-elementor-id=\"6545\" class=\"elementor elementor-6545\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-2b6b4ef elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"2b6b4ef\" 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-36c3d1c\" data-id=\"36c3d1c\" 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-59b0cd9 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"59b0cd9\" 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-2c5d67f\" data-id=\"2c5d67f\" 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-75fafc9 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"75fafc9\" 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-836e7b8\" data-id=\"836e7b8\" 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-5fb8c52 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"5fb8c52\" 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\/M%C3%A9thode_de_Brzozowski_et_McCluskey\" 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-ee8516d elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"ee8516d\" 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-abce6a7\" data-id=\"abce6a7\" 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-d43d8b1 elementor-widget elementor-widget-progress\" data-id=\"d43d8b1\" 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-d43d8b1\">\n\t\t\t\tDificultad\t\t\t<\/span>\n\t\t\n\t\t<div aria-labelledby=\"elementor-progress-bar-d43d8b1\" class=\"elementor-progress-wrapper\" role=\"progressbar\" aria-valuemin=\"0\" aria-valuemax=\"100\" aria-valuenow=\"80\" aria-valuetext=\"80% (DIfficile)\">\n\t\t\t<div class=\"elementor-progress-bar\" data-max=\"80\">\n\t\t\t\t<span class=\"elementor-progress-text\">Duro<\/span>\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-progress-percentage\">80%<\/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-6490ed1c elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"6490ed1c\" 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-472dbd75\" data-id=\"472dbd75\" 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-6487506c elementor-widget elementor-widget-text-editor\" data-id=\"6487506c\" 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\/algoritmo-brzozowski-y-mccluskey\/#Algorithme-de-Brzozowski-et-McCluskey\" >Algoritmo de Brzozowski y McCluskey<\/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\/algoritmo-brzozowski-y-mccluskey\/#Reduction-de-lautomate\" >Reducci\u00f3n de aut\u00f3matas<\/a><\/li><\/ul><\/nav><\/div>\n<h2><span class=\"ez-toc-section\" id=\"Algorithme-de-Brzozowski-et-McCluskey\"><\/span>Algoritmo de Brzozowski y McCluskey<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>El algoritmo de Brzozowski y McCluskey hace un uso intensivo de la representaci\u00f3n gr\u00e1fica del aut\u00f3mata. El aut\u00f3mata mismo es generalizado, permitiendo, como etiquetas de transici\u00f3n, no solo letras, sino <a href=\"https:\/\/complex-systems-ai.com\/es\/teoria-del-lenguaje\/lenguajes-regulares-y-expresiones-regulares\/\">expresiones regulares<\/a>. A partir de un <a href=\"https:\/\/complex-systems-ai.com\/es\/teoria-del-lenguaje\/\">aut\u00f3mata<\/a> terminado, eliminamos progresivamente los estados, y al final, terminamos con un aut\u00f3mata que tiene una sola transici\u00f3n. La etiqueta de esta transici\u00f3n es una expresi\u00f3n regular para el lenguaje reconocido por el aut\u00f3mata.<\/p>\n\n<p>Un aut\u00f3mata generalizado se define como un aut\u00f3mata finito no determinista tradicional, con las siguientes peculiaridades:<\/p>\n\n<ul class=\"wp-block-list\">\n<li>tiene solo un estado inicial \u03b1 y solo un estado final \u03c9<\/li>\n<li>las transiciones est\u00e1n etiquetadas con expresiones regulares<\/li>\n<li>ninguna transici\u00f3n entra en \u03b1 y ninguna transici\u00f3n sale del estado final \u03c9.<\/li>\n<\/ul>\n\n<p>Podemos transformar f\u00e1cilmente un aut\u00f3mata ordinario\u00a0<i>PARA<\/i>\u00a0en un aut\u00f3mata generalizado: basta con sumar los estados \u03b1 y \u03c9 y \u03b5-transiciones de \u03b1 a los estados iniciales de\u00a0<i>PARA<\/i>, y \u03b5-transiciones de los estados terminales de\u00a0<i>PARA<\/i>\u00a0a \u03c9.<\/p>\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Reduction-de-lautomate\"><\/span>Reducci\u00f3n de aut\u00f3matas<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n<p>Dado un aut\u00f3mata generalizado, calculamos un aut\u00f3mata generalizado que tiene menos transiciones o estados, aplicando las transformaciones siguientes sin modificar el lenguaje reconocido. Al final, solo existen los dos estados \u03b1 y \u03c9 y una transici\u00f3n de \u03b1 y \u03c9 cuya etiqueta es una expresi\u00f3n regular que denota el lenguaje reconocido. Las transformaciones son reducciones en las transiciones y reducciones en los estados.<\/p>\n\n<p>Para reducir un estado, se deben realizar todos los caminos que pasan a trav\u00e9s de este estado (a un estado adyacente). El idioma reconocido por esta ruta se agrega luego al PLC reducido (ver el ejemplo).<\/p>\n\n<p>El siguiente ejemplo muestra las principales reducciones posibles as\u00ed como las expresiones regulares generadas en el aut\u00f3mata:<\/p>\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" class=\"alignnone wp-image-6546\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/langage47.png\" alt=\"Algoritmo de Brzozowski y McCluskey\" width=\"220\" height=\"194\" title=\"\"><\/figure>\n\n<p>Lo que da el siguiente aut\u00f3mata generalizado:<\/p>\n\n<figure class=\"wp-block-image\"><img fetchpriority=\"high\" decoding=\"async\" class=\"alignnone wp-image-6547\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/langage48.png\" alt=\"Algoritmo de Brzozowski y McCluskey\" width=\"394\" height=\"194\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/langage48.png 394w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/langage48-300x148.png 300w\" sizes=\"(max-width: 394px) 100vw, 394px\" \/><\/figure>\n\n<p>Eliminamos q2: la ruta q0 -&gt; q2 -&gt; q3 da como resultado el lenguaje a\u00b2, por lo que se agrega a la ruta q0 -&gt; q3. La ruta q3 -&gt; q2 -&gt; q3 da el lenguaje ba o (ba) * porque es un bucle en q3 -&gt; q3<\/p>\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" class=\"alignnone wp-image-6548\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/langage49.png\" alt=\"Algoritmo de Brzozowski y McCluskey\" width=\"376\" height=\"201\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/langage49.png 376w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/langage49-300x160.png 300w\" sizes=\"(max-width: 376px) 100vw, 376px\" \/><\/figure>\n\n<p>Eliminamos q1: aqu\u00ed el bucle en q1 dar\u00e1 un a *<\/p>\n\n<figure class=\"wp-block-image\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-6549\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/langage50.png\" alt=\"Algoritmo de Brzozowski y McCluskey\" width=\"391\" height=\"90\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/langage50.png 391w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/langage50-300x69.png 300w\" sizes=\"(max-width: 391px) 100vw, 391px\" \/><\/figure>\n\n<p>Eliminamos q0:<\/p>\n\n<figure class=\"wp-block-image\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-6550\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/langage51.png\" alt=\"Algoritmo de Brzozowski y McCluskey\" width=\"309\" height=\"84\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/langage51.png 309w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/langage51-300x82.png 300w\" sizes=\"(max-width: 309px) 100vw, 309px\" \/><\/figure>\n\n<p>Eliminamos q3:<\/p>\n\n<figure class=\"wp-block-image\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-6551\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/langage52.png\" alt=\"Algoritmo de Brzozowski y McCluskey\" width=\"242\" height=\"61\" title=\"\"><\/figure>\n\n<p>N\u00f3tese que la expresi\u00f3n obtenida tambi\u00e9n depende del orden de eliminaci\u00f3n, pero que todos los lenguajes generados son iguales.<\/p>\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 P\u00e1gina de inicio Wiki Dificultad HARD 80% Algoritmo de Brzozowski y McCluskey El algoritmo de Brzozowski y McCluskey hace un uso intensivo de \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-6545","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/6545","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=6545"}],"version-history":[{"count":7,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/6545\/revisions"}],"predecessor-version":[{"id":18649,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/6545\/revisions\/18649"}],"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=6545"}],"curies":[{"name":"gracias","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}