{"id":6377,"date":"2018-05-31T10:36:31","date_gmt":"2018-05-31T09:36:31","guid":{"rendered":"http:\/\/smart--grid.net\/?page_id=6377"},"modified":"2022-12-03T23:00:32","modified_gmt":"2022-12-03T22:00:32","slug":"automate-avec-transition-vide","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/es\/teoria-del-lenguaje\/automata-con-transicion-vacia\/","title":{"rendered":"PLC con transici\u00f3n vac\u00eda"},"content":{"rendered":"<div data-elementor-type=\"wp-page\" data-elementor-id=\"6377\" class=\"elementor elementor-6377\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-28c9fc4 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"28c9fc4\" 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-fbc1925\" data-id=\"fbc1925\" 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-06655e2 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"06655e2\" 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-0c89454\" data-id=\"0c89454\" 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-5cac201 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"5cac201\" 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-b557c05\" data-id=\"b557c05\" 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-6a72dc7 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"6a72dc7\" 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\/Automate_fini_non_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-996fbed elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"996fbed\" 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-f3578c8\" data-id=\"f3578c8\" 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-d13815e elementor-widget elementor-widget-progress\" data-id=\"d13815e\" 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-d13815e\">\n\t\t\t\tDificultad\t\t\t<\/span>\n\t\t\n\t\t<div aria-labelledby=\"elementor-progress-bar-d13815e\" 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-6c1503a6 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"6c1503a6\" 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-1c25db91\" data-id=\"1c25db91\" 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-54701ae1 elementor-widget elementor-widget-text-editor\" data-id=\"54701ae1\" 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\/automata-con-transicion-vacia\/#Automate-avec-transition-vide\" >PLC con transici\u00f3n vac\u00eda<\/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\/automata-con-transicion-vacia\/#De-lautomate-avec-transition-vide-aux-mots-reconnus\" >De PLC con transici\u00f3n vac\u00eda a palabras reconocidas<\/a><\/li><\/ul><\/nav><\/div>\n<h2><span class=\"ez-toc-section\" id=\"Automate-avec-transition-vide\"><\/span>PLC con transici\u00f3n vac\u00eda<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>Estamos acostumbrados a dibujar un <a href=\"https:\/\/complex-systems-ai.com\/es\/teoria-del-lenguaje\/\">aut\u00f3mata<\/a> con transici\u00f3n vac\u00eda, representando los estados con c\u00edrculos, indicando el estado inicial con una flecha de entrada, los estados de aceptaci\u00f3n con un doble c\u00edrculo o una flecha de salida, y la transici\u00f3n del estado q al estado q&#039; leyendo la letra \u03b1 con una flecha que va de q a q&#039; y est\u00e1 etiquetada con \u03b1.<\/p>\n<p><\/p>\n<div style=\"padding: 5px; background-color: #d5edff; border: 2px solid #3c95e8; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\">\n<p>Un aut\u00f3mata finito A con transici\u00f3n \u00e9psilon (o aut\u00f3mata con transici\u00f3n vac\u00eda) es un triplete (Vt, Q, T) donde<\/p>\n<ul>\n<li>Vt es el vocabulario del aut\u00f3mata;<\/li>\n<li>Q es el conjunto finito de estados del aut\u00f3mata;<\/li>\n<li>T: Q \u00d7 (Vt \u222a \u03b5) \u2192 Q, es un mapa parcial llamado funci\u00f3n de transici\u00f3n del aut\u00f3mata.<\/li>\n<\/ul>\n<\/div>\n<p><\/p>\n<p>Tenga en cuenta que la notaci\u00f3n q (\u03b1) \u2192 q &#039;se vuelve ambigua, ya que ahora toma dos significados diferentes dependiendo de si \u03b1 se considera como una letra (o como el s\u00edmbolo \u03b5) y entonces habr\u00e1 una sola transici\u00f3n, o como una palabra. (de longitud 1 o 0), y entonces puede haber un n\u00famero arbitrario de transiciones (de las cuales como m\u00e1ximo una no estar\u00e1 vac\u00eda).<\/p>\n<p><\/p>\n<p>Una vez m\u00e1s, las nociones de derivaci\u00f3n no han cambiado, y la de \u00e1rbol de derivaci\u00f3n<br \/>requiere solo una adaptaci\u00f3n trivial, ya que ahora hay transiciones etiquetadas por \u03b5. Los c\u00e1lculos de un aut\u00f3mata con transiciones vac\u00edas permiten el paso a trav\u00e9s de cualquier n\u00famero de transiciones vac\u00edas durante la ejecuci\u00f3n. Por lo tanto, el n\u00famero de estados escaneados ya no ser\u00e1 igual al n\u00famero de letras de la palabra de entrada, sino que puede ser mucho mayor. El \u00e1rbol de c\u00e1lculo de un aut\u00f3mata con transiciones vac\u00edas resulta ser una herramienta menos interesante que para los aut\u00f3matas no deterministas sin transiciones vac\u00edas.<\/p>\n<p><\/p>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"De-lautomate-avec-transition-vide-aux-mots-reconnus\"><\/span>De PLC con transici\u00f3n vac\u00eda a palabras reconocidas<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\n<p>El proceso es el mismo que el del \u00e1rbol creado por un aut\u00f3mata no determinista. Notemos que adem\u00e1s de tener que crear nuevas ramas en caso de indeterminismo, tambi\u00e9n es necesario pasar por las transiciones de los estados sucesores por \u00e9psilon-transici\u00f3n.<\/p>\n<p><\/p>\n<p>Si tomamos el aut\u00f3mata anterior sobre la palabra aaaab:<\/p>\n<p><\/p>\n<p>p (aaaab) \u2192 q (aaab) \u2192 r (aaab) \u2192 s (aaab) \u2192 s (aab) \u2192 s (ab) \u2192 s (b) \u2192 q (b) \u2192 r - estado terminal<\/p>\n<p><\/p>\n<p>Es complejo calcular las palabras de longitud n reconocidas por un PLC con transici\u00f3n \u00e9psilon, entonces es necesario cerrar el PLC.<\/p>\n<p><\/p>\n<p>El principio del algoritmo consiste en reemplazar cada camino de longitud 1 que comienza con una transici\u00f3n \u00e9psilon por una nueva transici\u00f3n que describe este camino.<\/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=\"PLC con transici\u00f3n vac\u00eda\" width=\"400\" height=\"171\" title=\"\"><\/figure>\n<\/div>\n<p><\/p>\n<p>Hay dos caminos de longitud 1 que comienzan con la transici\u00f3n en \u00e9psilon:<\/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>Agregamos al aut\u00f3mata dos nuevas transiciones que resumen estos dos caminos:<\/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>Y eliminamos la transici\u00f3n (1, \u03b5, 3).<\/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=\"PLC con transici\u00f3n vac\u00eda\" width=\"373\" height=\"220\" title=\"\"><\/figure>\n<\/div>\n<p><\/p>\n<p>El algoritmo es un poco m\u00e1s complejo en los casos en los que se suceden varias transiciones \u00e9psilon y si pasan a un estado final, pero el principio general aqu\u00ed presentado sigue siendo v\u00e1lido (basta con aplicar el primer paso).<\/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>Teor\u00eda de los lenguajes P\u00e1gina de inicio Wiki Dificultad F\u00e1cil 25% Aut\u00f3mata con transici\u00f3n vac\u00eda Solemos dibujar un aut\u00f3mata con transici\u00f3n vac\u00eda, calculando \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-6377","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/6377","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=6377"}],"version-history":[{"count":3,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/6377\/revisions"}],"predecessor-version":[{"id":18598,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/6377\/revisions\/18598"}],"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=6377"}],"curies":[{"name":"gracias","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}