{"id":6405,"date":"2018-06-12T12:58:15","date_gmt":"2018-06-12T11:58:15","guid":{"rendered":"http:\/\/smart--grid.net\/?page_id=6405"},"modified":"2022-12-03T23:00:42","modified_gmt":"2022-12-03T22:00:42","slug":"automate-a-pile","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/es\/teoria-del-lenguaje\/automata-a-bateria\/","title":{"rendered":"Aut\u00f3mata con pilas"},"content":{"rendered":"<div data-elementor-type=\"wp-page\" data-elementor-id=\"6405\" class=\"elementor elementor-6405\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-28d6759 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"28d6759\" 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-52fe0e0\" data-id=\"52fe0e0\" 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-3ad16e1 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"3ad16e1\" 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-f246edf\" data-id=\"f246edf\" 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-447c0b6 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"447c0b6\" 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-79c8687\" data-id=\"79c8687\" 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-dab97fc elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"dab97fc\" 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_%C3%A0_pile\" 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-5f2efcc elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"5f2efcc\" 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-3a6b34e\" data-id=\"3a6b34e\" 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-7e52715 elementor-widget elementor-widget-progress\" data-id=\"7e52715\" 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-7e52715\">\n\t\t\t\tDificultad\t\t\t<\/span>\n\t\t\n\t\t<div aria-labelledby=\"elementor-progress-bar-7e52715\" 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-75ddc080 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"75ddc080\" 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-25522c77\" data-id=\"25522c77\" 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-3035d2a6 elementor-widget elementor-widget-text-editor\" data-id=\"3035d2a6\" 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<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-a-bateria\/#Automate-a-pile\" >Aut\u00f3mata con pilas<\/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-a-bateria\/#Exemple\" >Ejemplo<\/a><\/li><\/ul><\/nav><\/div>\n<h2><span class=\"ez-toc-section\" id=\"Automate-a-pile\"><\/span>Aut\u00f3mata con pilas<span class=\"ez-toc-section-end\"><\/span><\/h2><p>Los lenguajes libres de contexto, descritos por gram\u00e1ticas libres de contexto, son reconocidos (aceptados) por aut\u00f3matas pushdown. De manera informal, un <a href=\"https:\/\/complex-systems-ai.com\/es\/teoria-del-lenguaje\/\">aut\u00f3mata<\/a> alimentado por bater\u00eda es un aut\u00f3mata finito al que se le ha agregado una bater\u00eda inicialmente vac\u00eda de capacidad ilimitada. La ejecuci\u00f3n de un aut\u00f3mata pushdown sobre una palabra dada es similar a la de un aut\u00f3mata finito. Sin embargo, en cada paso, el aut\u00f3mata pushdown consulta la parte superior de su pila y eventualmente la reemplaza con una serie de s\u00edmbolos.<\/p><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;\"><p>Un aut\u00f3mata a bater\u00eda es un quintillizo A = (T, P, Q, M, S0) tal que:<\/p><ul><li>T es el vocabulario terminal,<\/li><li>P es el vocabulario de la pila (que contiene en particular un s\u00edmbolo de pila vac\u00edo inicial, anotado \u22a5),<\/li><li>Q es un conjunto finito de estados,<\/li><li>M es un conjunto de transiciones,<\/li><li>S0 \u2208 Q es el estado inicial.<\/li><\/ul><\/div><p>El vocabulario de la pila contiene todos los s\u00edmbolos que pueden aparecer en la pila y no es necesariamente distinto del vocabulario terminal (podemos tener T \u2229 P \u2260 \u2205).<\/p><p>Una transici\u00f3n de estado a pila es similar a la de una m\u00e1quina de estado, excepto que adem\u00e1s especifica el manejo de la pila. Una transici\u00f3n de M tiene la forma<br \/>(estado, symbol_lu, top_stack) \u2192 (new_state, action_on_stack) como:<\/p><ul><li>state y new_state son estados de Q,<\/li><li>symbol_lu es un s\u00edmbolo terminal de T, o, lo que significa que el aut\u00f3mata no mira la palabra,<\/li><li>stack_top es un s\u00edmbolo de P, o, lo que significa que el aut\u00f3mata no mira en la parte superior de la pila,<\/li><li>action_on_ stack es:<br \/>&quot;Pop el s\u00edmbolo en la parte superior de la pila&quot;, o<br \/>&quot;Coloca el s\u00edmbolo en la parte superior de la pila y luego apila una serie de s\u00edmbolos&quot; o<br \/>&quot;Apila una serie de s\u00edmbolos&quot;, o<br \/>&quot;no hacer nada&quot;.<\/li><\/ul><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;\"><p>El funcionamiento del aut\u00f3mata A = (T, P, Q, M, S0) se define como<br \/>siguiente, pr\u00f3ximo :<\/p><ul><li>Una configuraci\u00f3n de aut\u00f3mata se caracteriza por un triplete: (S, m, p) con S \u2208 Q, m \u2208 T<sup>\u2217<\/sup> y p \u2208 P<sup>\u2217<\/sup> es decir, un estado actual S, una serie m de s\u00edmbolos terminales (correspondientes al final de la palabra a analizar) y una serie p de s\u00edmbolos de pila (correspondientes al estado actual de la pila).<\/li><\/ul><\/div><p>La configuraci\u00f3n (S0, m0, p0) se puede diferenciar en un paso de la configuraci\u00f3n (S, m, p)<br \/>(denotado (S, m, p) \u21d2 (S0, m0, p0)) si: (S, u, v) \u2192 (S0, action_on_pile) es una transici\u00f3n de M, m = u.m0 (la palabra m para analizar comienza con el s\u00edmbolo u), el s\u00edmbolo en la parte superior de la pila p es v. p0 es la pila obtenida despu\u00e9s de realizar la acci\u00f3n action_on_pile en la pila p.<\/p><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;\">La palabra w es aceptada por el aut\u00f3mata de bater\u00eda A si (S0, w, \u22a5) \u21d2 (S, \u03b5, \u22a5) donde \u22a5 es el s\u00edmbolo de bater\u00eda vac\u00eda. El lenguaje L (A) aceptado por el PLC A a bater\u00eda es el conjunto de palabras aceptado por A.<\/div><p>En otras palabras, el aut\u00f3mata acepta una palabra si hay una serie de transiciones desde el estado inicial y la pila vac\u00eda, lo que lleva a la lectura completa de la palabra y nuevamente a la pila vac\u00eda. Tenga en cuenta que algunos PLC alimentados por bater\u00eda pueden aceptar estados finales sin una bater\u00eda descargada. Adem\u00e1s, cualquier aut\u00f3mata que reconoce por estado final tiene un aut\u00f3mata equivalente que reconoce por bater\u00eda descargada.<\/p><p>Los aut\u00f3matas alimentados por bater\u00eda que hemos definido aceptan una palabra cuando hay una rama que conduce a una configuraci\u00f3n en la que la pila est\u00e1 vac\u00eda y la palabra se lee por completo. Por esta raz\u00f3n, se denominan aut\u00f3matas apilados que aceptan en una pila vac\u00eda. Otra definici\u00f3n de aut\u00f3matas apilados es la de aut\u00f3matas apilados que aceptan en el estado final. Tal aut\u00f3mata tambi\u00e9n especifica un conjunto F \u2286 Q de estados finales. Se acepta una palabra si hay una derivaci\u00f3n que conduce a una configuraci\u00f3n en la que el estado es final (la pila no necesariamente est\u00e1 vac\u00eda).<\/p><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;\">Se dice que un aut\u00f3mata alimentado por bater\u00eda es determinista si cualquier situaci\u00f3n o configuraci\u00f3n dada corresponde a m\u00e1s de una transici\u00f3n.<\/div><p>Hay lenguajes libres de contexto que no son aceptados por ning\u00fan aut\u00f3mata push-down determinista. Los lenguajes aceptados por los aut\u00f3matas deterministas apilados, por lo tanto, forman una subclase de lenguajes libres de contexto: la clase de lenguajes deterministas libres de contexto.<\/p><h2><span class=\"ez-toc-section\" id=\"Exemple\"><\/span>Ejemplo<span class=\"ez-toc-section-end\"><\/span><\/h2><p>A continuaci\u00f3n se muestra un ejemplo de un aut\u00f3mata apilado no determinista. Deje que el aut\u00f3mata de empuje hacia abajo reconozca el lenguaje de palabras formadas en {a, b} y que contienen el mismo n\u00famero de a y b: A = (T, P, Q, M, q) tal que: T = {a, b }, P = {a, b}, Q = {q} y la siguiente matriz de transici\u00f3n M<\/p><p><img decoding=\"async\" class=\"aligncenter wp-image-6406 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/06\/langage23.png\" alt=\"Aut\u00f3mata con pilas\" width=\"307\" height=\"143\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/06\/langage23.png 307w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/06\/langage23-300x140.png 300w\" sizes=\"(max-width: 307px) 100vw, 307px\" \/><\/p><p>La operaci\u00f3n de este aut\u00f3mata sobre la palabra w = aabbabba es:<\/p><p><img decoding=\"async\" class=\"aligncenter wp-image-6407 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/06\/langage24.png\" alt=\"Aut\u00f3mata con pilas\" width=\"171\" height=\"181\" title=\"\"><\/p><p>En cuanto a los aut\u00f3matas finitos, podemos dar a los aut\u00f3matas pushdown una representaci\u00f3n por <a href=\"https:\/\/complex-systems-ai.com\/es\/teoria-de-grafos\/\">grafico<\/a>. Los arcos tienen la siguiente informaci\u00f3n:<\/p><ul><li>s\u00edmbolo de lectura, s\u00edmbolo sin apilar; s\u00edmbolo apilado.<\/li><\/ul><p>Por ejemplo el arco a, A; \u03b5 leer\u00e1 el s\u00edmbolo a siempre que pueda colocar un s\u00edmbolo A en la parte superior de la pila. Tenga en cuenta que \u03b5 o \u03bb representan &quot;no hacer nada&quot;.<\/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 del lenguaje P\u00e1gina de inicio Wiki Dificultad Media 50% Aut\u00f3mata pushdown Los lenguajes libres de contexto, descritos por gram\u00e1ticas libres de contexto, son reconocidos (aceptados) por... <\/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-6405","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/6405","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=6405"}],"version-history":[{"count":3,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/6405\/revisions"}],"predecessor-version":[{"id":18615,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/6405\/revisions\/18615"}],"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=6405"}],"curies":[{"name":"gracias","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}