{"id":6358,"date":"2018-05-31T10:13:41","date_gmt":"2018-05-31T09:13:41","guid":{"rendered":"http:\/\/smart--grid.net\/?page_id=6358"},"modified":"2022-12-03T23:00:30","modified_gmt":"2022-12-03T22:00:30","slug":"automate-fini-non-deterministe","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/es\/teoria-del-lenguaje\/automata-finito-no-determinista\/","title":{"rendered":"Aut\u00f3mata finito no determinista"},"content":{"rendered":"<div data-elementor-type=\"wp-page\" data-elementor-id=\"6358\" class=\"elementor elementor-6358\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-793f198 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"793f198\" 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-e2035fa\" data-id=\"e2035fa\" 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-4f455f5 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"4f455f5\" 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-b38f307\" data-id=\"b38f307\" 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-dcb5f1d elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"dcb5f1d\" 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-2327628\" data-id=\"2327628\" 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-e1d8a32 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"e1d8a32\" 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-f7c9104 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"f7c9104\" 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-b814a09\" data-id=\"b814a09\" 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-aebd61c elementor-widget elementor-widget-progress\" data-id=\"aebd61c\" 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-aebd61c\">\n\t\t\t\tDificultad\t\t\t<\/span>\n\t\t\n\t\t<div aria-labelledby=\"elementor-progress-bar-aebd61c\" 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-436c7815 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"436c7815\" 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-5e0e6d99\" data-id=\"5e0e6d99\" 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-1f84f110 elementor-widget elementor-widget-text-editor\" data-id=\"1f84f110\" 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-finito-no-determinista\/#Automate-fini-non-deterministe\" >Aut\u00f3mata finito no determinista<\/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-finito-no-determinista\/#Non-determinisme-et-mots-reconnus\" >No determinismo y palabras reconocidas<\/a><\/li><\/ul><\/nav><\/div>\n<h2><span class=\"ez-toc-section\" id=\"Automate-fini-non-deterministe\"><\/span>Aut\u00f3mata finito no determinista<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> finito no determinista, 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 por 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 no determinista A 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 \u2192 Q, es una aplicaci\u00f3n parcial llamada funci\u00f3n de transici\u00f3n del aut\u00f3mata.<\/li>\n<\/ul>\n<\/div>\n<p><\/p>\n<p>Tenga en cuenta que un aut\u00f3mata determinista es un caso particular de un aut\u00f3mata no determinista que asocia con cualquier elemento de Q \u00d7 Vt una parte de Q que tiene cero o un elemento (exactamente uno si es un aut\u00f3mata completo). De un aut\u00f3mata determinista podemos decir que est\u00e1 incompleto si se puede bloquear, es decir, si existe un estado q y una letra a tal que T (q, a) = \u2205. Si est\u00e1 completo, tenemos la siguiente propiedad:<\/p>\n<p><\/p>\n<div style=\"padding: 5px; background-color: #ffdcd3; border: 2px solid #ff7964; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\">\n<p>Sea A = (Vt, Q, T) un aut\u00f3mata finito no determinista completo. Entonces, para cualquier palabra u \u2208 V<sup>\u2217<\/sup><sub>t<\/sub> y cualquier estado q \u2208 Q, existe un estado (no siempre \u00fanico) q &#039;\u2208 Q tal que q (u) \u2192 Aq&#039;.<\/p>\n<\/div>\n<p><\/p>\n<p>Sin embargo, lo no determinista tiene una consecuencia esencial: puede haber varias derivaciones resultantes del estado inicial i que leen una palabra dada w, algunas de las cuales pueden bloquearse y otras no, y en el \u00faltimo caso algunas pueden terminar en el estado de aceptaci\u00f3n y otros no. La aceptaci\u00f3n tiene lugar si hay al menos un c\u00e1lculo exitoso. Si todos los c\u00e1lculos fallan, no habr\u00e1 otra forma de averiguarlo que explorarlos todos antes de saber que la palabra w no coincide. Por tanto, la noci\u00f3n correcta no es la de c\u00e1lculo, sino la de un \u00e1rbol de c\u00e1lculo asociado a una palabra le\u00edda por el aut\u00f3mata:<\/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>Dado un aut\u00f3mata finito no determinista A, el \u00e1rbol de derivaci\u00f3n con ra\u00edz q \u2208 Q generado al leer la palabra u es un <a href=\"https:\/\/complex-systems-ai.com\/es\/teoria-de-grafos\/arboles-y-arboles\/\">\u00e1rbol<\/a> doblemente etiquetado definido por inducci\u00f3n en u:<br \/>Si u = \u03b5, entonces el \u00e1rbol se reduce a su ra\u00edz q;<br \/>Si u = av, la ra\u00edz q tiene transiciones salientes etiquetadas por a \u2208 Vt a diferentes \u00e1rboles computacionales generados por la lectura de v y cuyas ra\u00edces est\u00e1n etiquetadas por los estados de T (q, a).<\/p>\n<\/div>\n<p><\/p>\n<p>Un \u00e1rbol de derivaci\u00f3n se construye como en el caso de un aut\u00f3mata determinista. En el caso de un aut\u00f3mata finito no determinista, no es lineal y puede presentar varias ramas que dar\u00e1n varias derivaciones que conduzcan o no al reconocimiento de la palabra.<\/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>Una palabra u es reconocida por un aut\u00f3mata no determinista A si una de las hojas de su \u00e1rbol de c\u00e1lculo est\u00e1 etiquetada con un estado de aceptaci\u00f3n.<\/p>\n<\/div>\n<p><\/p>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Non-determinisme-et-mots-reconnus\"><\/span>No determinismo y palabras reconocidas<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\n<p>Consideramos el siguiente aut\u00f3mata finito no determinista A = ({a, b}, {1, 2, 3}, \u2206, {1}, {1}):<\/p>\n<p><\/p>\n<div>\n<figure><img decoding=\"async\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/05\/langage7.png\" alt=\"aut\u00f3mata finito no determinista\" width=\"263\" height=\"171\" title=\"\"><\/figure>\n<\/div>\n<p><\/p>\n<p>\u00bfEl aut\u00f3mata A acepta la palabra baabab?<\/p>\n<p><\/p>\n<div>\n<figure><img decoding=\"async\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/05\/langage8.png\" alt=\"aut\u00f3mata finito no determinista\" width=\"143\" height=\"260\" title=\"\"><\/figure>\n<\/div>\n<p><\/p>\n<p>Ninguna hoja corresponde a un estado final, tenga en cuenta que todas las hojas terminan en el pozo.<\/p>\n<p><\/p>\n<p>Al igual que el aut\u00f3mata determinista, es posible construir las palabras reconocidas por el aut\u00f3mata mirando las l\u00edneas de entrada y las columnas de salida. Las palabras de longitudes n se construyen luego elevando la matriz de transici\u00f3n a la potencia de n.<\/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 P\u00e1gina de inicio Dificultad F\u00e1cil 25% Aut\u00f3mata finito no determinista Estamos acostumbrados a dibujar un aut\u00f3mata finito no determinista, mostrando los estados ... <\/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-6358","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/6358","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=6358"}],"version-history":[{"count":3,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/6358\/revisions"}],"predecessor-version":[{"id":18589,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/6358\/revisions\/18589"}],"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=6358"}],"curies":[{"name":"gracias","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}