Introduction to Automata

Pushdown Automata Introduction

A pushdown automaton (PDA) is a way to implement a context-free grammar (CFG) in a similar way we design Finite Automata (FA) for a regular grammar (RG). A DFA has limited memory, but a PDA can hold unlimited memory.

Basically, a Pushdown Automaton is

“Finite Automata Machine” + “a stack”, where

  • FA represents a finite memory for a finite number of states
  • A stack is an extra memory with infinite size to PUSH and POP values.

Operation of Pushdown Automata

There are two basic Operations in Pushdown Automata.

1. PUSH: It means inserting a new input symbol into the stack.

2. POP: It means removing an input symbol from the stack.

Pushdown Automata Operations

Note: PUSH and POP operations are always performed on the top of a stack

Components of Pushdown Automata

A pushdown automaton has 3 basic components

  • Input tape: It contains the input string.
  • Control unit: It takes an input and forwards it to the stack for PUSH or POP.
  • Stack: It is the memory of infinite size.

The following diagram explains the above components.

Components of Pushdown Automata

Note: A PDA may or may not PUSH or POP an input symbol in every transition. But PDA has to read the top of the stack in every transition.

7-Tuples of Pushdown Automata

Pushdown Automata (PDA) can be formally described by 7-tuples (Q, ∑, Γ, δ, q0, Z0, F)

  • Qis, the finite number of states,
  • is the input alphabet, which is PUSH or POP from Stack.
  • Γis stack symbols.
  • Transition function: Q × (∑ ∪ {ε}) x Γ à Q × Γ * // where Q is any state ∑ is the input symbol, ε is epsilon, Γ is the top of the stack value, and Γ * represents all symbols existing in the stack.
  • q0 is the start state (q0 ∈ Q)
  • Z0 is the default value of the stack. It is used to represent the Null value of the stack. We can say Z0 is an epsilon.
  • Fis a set of Final states (F ∈ Q). Final states may or may not exist in PDA.

Transition Function in PDA

The transition function depends on the current state and three symbols

  • Input symbol
  • Stack Top Symbol
  • Push Symbol

The Value of any symbol (Input stack or push) can be epsilon (∈).

Let us see the following diagram, which shows a transition in a PDA from a state q0 to state q1, labeled as x,y → z

Transition Function in PDA

This means at state q0, if we consume an input string ‘x’ and the top symbol of the stack is ‘y’, then we pop ‘y’ and push ‘z’ on top of the stack and move to the next state q1.