{"id":6516,"date":"2018-07-09T10:18:21","date_gmt":"2018-07-09T09:18:21","guid":{"rendered":"http:\/\/smart--grid.net\/?page_id=6516"},"modified":"2022-12-03T23:00:48","modified_gmt":"2022-12-03T22:00:48","slug":"algorithme-de-gloushkov","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/es\/teoria-del-lenguaje\/algoritmo-de-gloushkov\/","title":{"rendered":"El algoritmo de Gloushkov"},"content":{"rendered":"<div data-elementor-type=\"wp-page\" data-elementor-id=\"6516\" class=\"elementor elementor-6516\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-ae1079a elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"ae1079a\" 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-a3d9694\" data-id=\"a3d9694\" 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-e6caffd elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"e6caffd\" 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-9f924f2\" data-id=\"9f924f2\" 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-639a5bd elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"639a5bd\" 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-a79b57a\" data-id=\"a79b57a\" 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-54f8da9 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"54f8da9\" 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_de_Glushkov\" 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-c5b8aa2 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"c5b8aa2\" 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-899970b\" data-id=\"899970b\" 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-d6e03ef elementor-widget elementor-widget-progress\" data-id=\"d6e03ef\" 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-d6e03ef\">\n\t\t\t\tDificultad\t\t\t<\/span>\n\t\t\n\t\t<div aria-labelledby=\"elementor-progress-bar-d6e03ef\" 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\">F\u00e1cil<\/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-4b585f2c elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"4b585f2c\" 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-1cc84a70\" data-id=\"1cc84a70\" 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-6b06c9b7 elementor-widget elementor-widget-text-editor\" data-id=\"6b06c9b7\" 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\">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-de-gloushkov\/#Algorithme-de-Gloushkov\" >El algoritmo de Gloushkov<\/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-de-gloushkov\/#Etape-1-lettres-distinctes\" >Paso 1: letras separadas<\/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\/algoritmo-de-gloushkov\/#Etape-2-construction-de-lautomate\" >Paso 2: construcci\u00f3n del aut\u00f3mata<\/a><\/li><\/ul><\/nav><\/div>\n<h2><span class=\"ez-toc-section\" id=\"Algorithme-de-Gloushkov\"><\/span>El algoritmo de Gloushkov<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>El algoritmo de Glushkov construye un <a href=\"https:\/\/complex-systems-ai.com\/es\/teoria-del-lenguaje\/\">aut\u00f3mata<\/a> no determinista aceptando el conjunto de palabras descritas por una expresi\u00f3n regular. El n\u00famero de estados del aut\u00f3mata es proporcional al tama\u00f1o de la expresi\u00f3n.<\/p>\n<p><\/p>\n<p>Los pasos principales del algoritmo de Gloushkov a partir de una expresi\u00f3n regular E son los siguientes:<\/p>\n<p><\/p>\n<ol class=\"wp-block-list\">\n<li>Transforma la expresi\u00f3n E en una nueva expresi\u00f3n E &#039;donde cada letra aparece como m\u00e1ximo una vez en E&#039;.<\/li>\n<li>Construye un aut\u00f3mata A &#039;aceptando el conjunto de palabras descrito por E&#039;<\/li>\n<li>Transforma A &#039;en un aut\u00f3mata A aceptando el conjunto de palabras descrito por E reemplazando los s\u00edmbolos \u00fanicos de E&#039; por los originales<\/li>\n<\/ol>\n<p><\/p>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Etape-1-lettres-distinctes\"><\/span>Paso 1: letras separadas<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\n<p>El primer paso en el algoritmo de Glushkov es hacer que todas las letras de la expresi\u00f3n sean distintas. Cada aparici\u00f3n de la misma letra est\u00e1 numerada. La expresi\u00f3n E = (ab + b)<sup>*<\/sup>\u00a0se convierte, por ejemplo, en E &#039;= (ab<sub>0<\/sub>\u00a0+ b<sub>1<\/sub>)<sup>*<\/sup>.<\/p>\n<p><\/p>\n<p>Tomemos un ejemplo m\u00e1s largo: E = (a + b) * (abb + \u03b5). Despu\u00e9s de renombrar tenemos la siguiente expresi\u00f3n: (x<sub>1<\/sub>\u00a0+ x<sub>2<\/sub>) * (X<sub>3<\/sub>X<sub>4<\/sub>X<sub>5<\/sub>\u00a0+ \u03b5).<\/p>\n<p><\/p>\n<p>Ahora debemos definir el primer grupo que contiene los s\u00edmbolos que pueden comenzar una palabra. Por \u00faltimo, el grupo que contiene los s\u00edmbolos que pueden terminar la palabra. Y una siguiente tabla que define los s\u00edmbolos que pueden tener como sufijo otro s\u00edmbolo.<\/p>\n<p><\/p>\n<p>En este ejemplo tenemos:<\/p>\n<p><\/p>\n<ul class=\"wp-block-list\">\n<li>Prime = {x<sub>1<\/sub>, X<sub>2<\/sub>, X<sub>3<\/sub>}<\/li>\n<li>\u00daltimo = {x<sub>1<\/sub>, X<sub>2<\/sub>, X<sub>5<\/sub>}<\/li>\n<li>Tabla de lo siguiente:\u00a0<img decoding=\"async\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/langage30.png\" alt=\"Algoritmo de Glushkov\" width=\"161\" height=\"196\" title=\"\"><\/li>\n<\/ul>\n<p><\/p>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Etape-2-construction-de-lautomate\"><\/span>Paso 2: construcci\u00f3n del aut\u00f3mata<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\n<p>Sea E &#039;una expresi\u00f3n regular donde todas las letras son diferentes. Construimos un aut\u00f3mata A &#039;como sigue.<\/p>\n<p><\/p>\n<ul class=\"wp-block-list\">\n<li>El conjunto de estados es Q = {i} \u222a {a: a aparece en E &#039;}<\/li>\n<li>El estado inicial es el estado i<\/li>\n<li>Los estados finales son \u00daltimo (E &#039;) a los que agregamos i si \u03b5 \u2208 E&#039;<\/li>\n<li>Las transiciones son (i, a, a) para a \u2208 Prime (E &#039;) y (a, b, b) para (a, b) \u2208 Next (E&#039;)<\/li>\n<\/ul>\n<p><\/p>\n<p>En nuestra expresi\u00f3n (x<sub>1<\/sub>\u00a0+ x<sub>2<\/sub>) * (X<sub>3<\/sub>X<sub>4<\/sub>X<sub>5<\/sub>\u00a0+ \u03b5), construimos el estado inicial i con la transici\u00f3n x<sub>1<\/sub>, X<sub>2<\/sub>, X<sub>3<\/sub>\u00a0a los respectivos estados x<sub>1<\/sub>, X<sub>2<\/sub>, X<sub>3<\/sub>.<\/p>\n<p><\/p>\n<p>Luego usamos la siguiente tabla para crear los enlaces de tipo (a, b, b). Por ejemplo si tomamos la primera l\u00ednea tenemos los siguientes arcos: (x<sub>1<\/sub>, X<sub>1<\/sub>, X<sub>1<\/sub>), (X<sub>1<\/sub>, X<sub>2<\/sub>, X<sub>2<\/sub>), (X<sub>1<\/sub>, X<sub>3<\/sub>, X<sub>3<\/sub>).<\/p>\n<p><\/p>\n<p>Para terminar agregamos los estados terminales {x<sub>1<\/sub>, X<sub>2<\/sub>, X<sub>5<\/sub>}. Lo que finalmente da el siguiente aut\u00f3mata:<\/p>\n<p><\/p>\n<figure><img fetchpriority=\"high\" decoding=\"async\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/langage31.png\" alt=\"Algoritmo de Glushkov\" width=\"593\" height=\"358\" 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>Teor\u00eda de los lenguajes P\u00e1gina de inicio Wiki Dificultad F\u00e1cil 25% Algoritmo de Glushkov El algoritmo de Glushkov construye un aut\u00f3mata no determinista aceptando el conjunto de palabras descrito por \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-6516","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/6516","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=6516"}],"version-history":[{"count":3,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/6516\/revisions"}],"predecessor-version":[{"id":18636,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/6516\/revisions\/18636"}],"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=6516"}],"curies":[{"name":"gracias","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}