Battery operated automaton

Difficulty

Average 50%

Contents

Context-free languages, described by context-free grammars, are recognized (accepted) by pushdown automata. Informally, a automaton 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.

A battery-powered automaton is a quintuplet A = (T, P, Q, M, S0) such that:

T is the terminal vocabulary,
P is the stack vocabulary (containing in particular an initial empty stack symbol, noted ⊥),
Q is a finite set of states,
M is a set of transitions,
S0 ∈ Q is the initial state.

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 ∩ 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
(state, symbol_lu, top_stack) → (new_state, action_on_stack) such as:

state and new_state are states of Q,
symbol_lu is either a terminal symbol of T, or, meaning that the automaton does not look at the word,
stack_top is either a symbol of P, or, meaning that the automaton does not look at the top of the stack,
action_on_ stack is either:
“Pop the symbol at the top of the stack”, or
“Pop the symbol at the top of the stack then stack a series of symbols” or
“Stack a series of symbols”, or
“Do nothing”.

The operation of the automaton A = (T, P, Q, M, S0) is defined as
next :

An automaton configuration is characterized by a triplet: (S, m, p) with S ∈ Q, m ∈ T^∗ and p ∈ P^∗ 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).

The configuration (S0, m0, p0) can be differentiated in one step from the configuration (S, m, p)
(denoted (S, m, p) ⇒ (S0, m0, p0)) if: (S, u, v) → (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.

A word w is accepted by the battery automaton A if (S0, w, ⊥) ⇒ (S, ε, ⊥) where ⊥ is the empty battery symbol. The L (A) language accepted by the battery-operated PLC A is the set of words accepted by A.

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.

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 ⊆ 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).

A battery-powered automaton is said to be deterministic if any given situation or configuration corresponds to more than one transition.

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.

Example

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

The operation of this automaton on the word w = aabbabba is:

As for finite automata, pushdown automata can be given a representation by graph. Arcs have the following information:

read symbol, unstacked symbol; stacked symbol.

For example the arc a, A; ε will read the symbol a provided you can pop an A symbol at the top of the stack. Note that ε or λ represents "doing nothing".