{"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\/en\/language-theory\/battery-powered-automaton\/","title":{"rendered":"Battery operated automaton"},"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\/en\/language-theory\/\">\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\">Language theory<\/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\/en\/\">\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\">Home page<\/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\tDifficulty\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\">Average<\/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\">Contents<\/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=\"Toggle Table of Content\"><span class=\"ez-toc-js-icon-con\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Toggle<\/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\/en\/language-theory\/battery-powered-automaton\/#Automate-a-pile\" >Battery operated automaton<\/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\/en\/language-theory\/battery-powered-automaton\/#Exemple\" >Example<\/a><\/li><\/ul><\/nav><\/div>\n<h2><span class=\"ez-toc-section\" id=\"Automate-a-pile\"><\/span>Battery operated automaton<span class=\"ez-toc-section-end\"><\/span><\/h2><p>Context-free languages, described by context-free grammars, are recognized (accepted) by pushdown automata. Informally, a <a href=\"https:\/\/complex-systems-ai.com\/en\/language-theory\/\">automaton<\/a> battery-powered is a finite automaton to which an initially empty battery of unlimited capacity has been added. The execution of a pushdown automaton on a given word is similar to that of a finite automaton. However, at each step, the pushdown automaton consults the top of its stack and eventually replaces it with a series of symbols.<\/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>A battery-powered automaton is a quintuplet A = (T, P, Q, M, S0) such that:<\/p><ul><li>T is the terminal vocabulary,<\/li><li>P is the stack vocabulary (containing in particular an initial empty stack symbol, noted \u22a5),<\/li><li>Q is a finite set of states,<\/li><li>M is a set of transitions,<\/li><li>S0 \u2208 Q is the initial state.<\/li><\/ul><\/div><p>The stack vocabulary contains all the symbols that can appear on the stack, and is not necessarily distinct from the terminal vocabulary (we can have T \u2229 P \u2260 \u2205).<\/p><p>A state-to-stack transition is similar to that of a state machine, except that it additionally specifies the handling of the stack. A transition of M is of the form<br \/>(state, symbol_lu, top_stack) \u2192 (new_state, action_on_stack) such as:<\/p><ul><li>state and new_state are states of Q,<\/li><li>symbol_lu is either a terminal symbol of T, or, meaning that the automaton does not look at the word,<\/li><li>stack_top is either a symbol of P, or, meaning that the automaton does not look at the top of the stack,<\/li><li>action_on_ stack is either:<br \/>\u201cPop the symbol at the top of the stack\u201d, or<br \/>\u201cPop the symbol at the top of the stack then stack a series of symbols\u201d or<br \/>\u201cStack a series of symbols\u201d, or<br \/>\u201cDo nothing\u201d.<\/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>The operation of the automaton A = (T, P, Q, M, S0) is defined as<br \/>next :<\/p><ul><li>An automaton configuration is characterized by a triplet: (S, m, p) with S \u2208 Q, m \u2208 T<sup>\u2217<\/sup> and p \u2208 P<sup>\u2217<\/sup> that is to say, a current state S, a series m of terminal symbols (corresponding to the end of the word to be analyzed) and a series p of stack symbols (corresponding to the current state of the stack).<\/li><\/ul><\/div><p>The configuration (S0, m0, p0) can be differentiated in one step from the configuration (S, m, p)<br \/>(denoted (S, m, p) \u21d2 (S0, m0, p0)) if: (S, u, v) \u2192 (S0, action_on_pile) is a transition of M, m = u.m0 (the word m to analyze starts with the symbol u), the symbol at the top of the stack p is v. p0 is the stack obtained after performing the action_on_pile action on stack 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;\">A word w is accepted by the battery automaton A if (S0, w, \u22a5) \u21d2 (S, \u03b5, \u22a5) where \u22a5 is the empty battery symbol. The L (A) language accepted by the battery-operated PLC A is the set of words accepted by A.<\/div><p>In other words, a word is accepted by the automaton if there is a series of transitions from the initial state and empty stack, leading to the entire reading of the word and to the empty stack again. Note that some battery-powered PLCs can accept on final states without an empty battery. In addition, any automaton recognizing by final state has an equivalent automaton recognizing by empty battery.<\/p><p>The battery powered automata that we have defined accept a word when there is a branch leading to a configuration where the stack is empty and the word is fully read. For this reason, they are called stacked automata accepting on empty stack. Another definition of stacked automata is that of stacked automata accepting on final state. Such an automaton additionally specifies a set F \u2286 Q of final states. A word is accepted if there is a derivation leading to a configuration where the state is final (the stack not necessarily being empty).<\/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;\">A battery-powered automaton is said to be deterministic if any given situation or configuration corresponds to more than one transition.<\/div><p>There are context-free languages that are not accepted by any deterministic push-down automaton. The languages accepted by deterministic stacked automata therefore form a subclass of context-free languages: the class of deterministic context-free languages.<\/p><h2><span class=\"ez-toc-section\" id=\"Exemple\"><\/span>Example<span class=\"ez-toc-section-end\"><\/span><\/h2><p>Here is an example of a non-deterministic stacked automaton. Let the push-down automaton recognize the language of words formed on {a, b} and containing the same number of a and b: A = (T, P, Q, M, q) such that: T = {a, b}, P = {a, b}, Q = {q} and the following transition matrix 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=\"Battery operated automaton\" 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>The operation of this automaton on the word w = aabbabba is:<\/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=\"Battery operated automaton\" width=\"171\" height=\"181\" title=\"\"><\/p><p>As for finite automata, pushdown automata can be given a representation by <a href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-2\/\">graph<\/a>. Arcs have the following information:<\/p><ul><li>read symbol, unstacked symbol; stacked symbol.<\/li><\/ul><p>For example the arc a, A; \u03b5 will read the symbol a provided you can pop an A symbol at the top of the stack. Note that \u03b5 or \u03bb represents &quot;doing nothing&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>Language theory Home page Wiki Difficulty Medium 50% Pushdown automaton Context-free languages, described by context-free grammars, are recognized (accepted) by \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-6405","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/6405","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/comments?post=6405"}],"version-history":[{"count":3,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/6405\/revisions"}],"predecessor-version":[{"id":18615,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/6405\/revisions\/18615"}],"up":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/5028"}],"wp:attachment":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/media?parent=6405"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}