Pushdown automata Representation with solved examples

Representation of Pushdown automata:

The pushdown automaton is represented by the following types;

1. Transaction function of pushdown automata:
2. Graphical Notation of pushdown automata (PDA):

Transaction functions of pushdown automata:

The transaction function of pushdown automata has the following form;

δ: (Q x (Σ ∪{ε}) x X) → (p, γ)

δ is now a function of three arguments.

The first two arguments are the same as before:

(i) The state
(ii) The symbol of input alphabet or either ‘ε’ or ‘λ’.
(iii) The third argument is the symbol on top of the stack. Just as the input symbol is ‘consumed’ when the function is applied, the stack symbol is also “consumed” (removed from the stack).

Note:

• While the second argument may be ε, rather than a member of the input alphabet (so that no input symbol is consumed), there is no such option for the third argument.
• δ always consumes a symbol from the stack, no move is possible if the stack is empty.
• There may also be a ε-transition, where the second argument may be ε, which means that a move that does not consume an input symbol is possible. No move is possible if the stack is empty.

For example, let us consider the set of transition rules of a pushdown automaton given by

δ(q₁, a, b) = {(q₂ , cd), (q₃ , ε)}

If at any time the control unit is in state q₁, the input symbol read is ‘a’, and the symbol on the top of stack is ‘b’, then one of the following two cases can occur:

• The control unit tends to go into the state q₂ and the string ‘cd’ replaces ‘b’ on top of the stack.
• The control unit goes into state q₃ with the symbol b removed from the top of the stack.

In the deterministic case, when the function δ is applied, the automaton moves to a new state q∈Q and pushes a new string of symbols x∈Γ* onto the stack. As we are dealing with nondeterministic pushdown automaton, the result of applying δ is a finite set of (q, x) pairs.

Also check: Importance of finite automata

Graphical Notation of pushdown automata (PDA):

Pushdown automata are not usually drawn. However, with a few minor extensions, we can draw an PDA similar to the way we draw an finite automata. The graphical representation of the PDA’s consists;

1. The node corresponds to the states of the PDA.
2. An arrow labeled Start indicates the start state, and doubly circled states are final or accepting as for finite automata.
3. The arcs correspond to transition of the PDA in the following sense. An arc labeled a|X, u from state q to state p means that δ(q, a, X) contains the pair (p, u), perhaps among other pairs. That is, the arc label tells what input is used, and also gives the old and new tops of the stack.

In short instead of labeling an arc with an element of ∑, we can label arcs with a|x, y where a∈∑, x ∈ Γ and y ∈ Γ*.

Let us consider the pushdown given by

M = (Q={q₀, q₁, q₂, q₃}, ∑={a,b}, Γ={0,1}, δ, q₀ , z₀ = 0, F={q₃})

Where;

δ(q₀, a, 0) = {(q₁, 10), (q₃, ε)}
δ(q₀, ε, 0) = {(q₃, ε)}
δ(q₁, a, 1) = {(q₁, 11)}
δ(q₁, b, 1) = {(q₂, ε)}
δ(q₁, b, 1) = {(q₂, ε)}
δ(q₂, ε, 0) = {(q₃, ε)}

The Pushdown is drawn as follows;

Note: The top of the stack is considered to be the left, so that, for example, if we get an ‘a’ from the starting position, the stack changes from ‘0’ to ‘10.’.

Also check: software engineering vs system engineering