TOC-PDA

To access the infinite memory space, an NFA is upgraded by a stack. A stack has these basic operations.

  • Push
  • Pop

The computational model combines a finite state machine and a stack is called pushdown automata .

Pushdown automata

PDA

A pushdown automaton is a 6-tuple , where

  • is the finite set of states;
  • is the finite input alphabet;
  • is the finite stack alphabet;
  • is the transition function;
  • is the initial state;
  • is the set of final states;

The transition function is understood as

Transition Function

If:

  • The current state is
  • The next input symbol is
  • The symbol on top of the stack is

Then:

  • The next state is
  • The new stack symbol on the top is

PDA is defined from NFA.

  • is included in and .
  • The domain of is the power set .
  • has multiple choices for the next state.

Computation on PDA

An input string is accepted by a PDA if there exists a sequence of states and a sequence of strings such that:

  1. (where is the initial state);
  2. (the stack is empty initially);
  3. ( is a final state); and
  4. For ,
    where and for some and .

The last condition explains a transition.

  • Each string is the content of the stack.
  • The leftmost symbol in is at the bottom of the stack.
  • The rightmost symbol in is at the top of the stack ( and ).
  • The PDA consumes , changes the stack symbol from to , and shifts to state .

Example

A PDA for

PDA

Table Of Contents
TOC-PDA
PDA
Transition Function
Computation on PDA
Example