IV

Push Down Automata- Definition of the Pushdown Automaton, the Languages of a PDA,
Equivalence of PDA‘s and CFG‘s, Deterministic Pushdown Automata.

Introduction of Pushdown Automata

We are already familiar with finite automata. But finite automata can be used to accept only regular languages.
Pushdown Automata is a finite automata with extra memory called stack which helps Pushdown automata to
recognize Context Free Languages.

A Pushdown Automata (PDA) can be defined as :

• Q is the set of states
• ∑is the set of input symbols
• Γ is the set of pushdown symbols (which can be pushed and popped from stack)
• q0 is the initial state
• Z is the initial pushdown symbol (which is initially present in stack)
• F is the set of final states
• δ is a transition function which maps Q x {Σ ∪ ∈} x Γ into Q x Γ*. In a given state, PDA will read
input symbol and stack symbol (top of the stack) and move to a new state and change the symbol
of stack.

Transition Function:
Transition Function is an formal notation of how a PDA “computes” a input string and make a decision that string
is accepted or rejected.
TF is a triple (q, w, α), where:
1. q is the current state.
2. w is the remaining input.
3.α is the stack contents, top at the left.

Useful Notation:
⊢ sign is called a “turnstile notation” and represents
one move.
⊢* sign represents a sequence of moves.
Eg- (p, b, T) ⊢ (q, w, α)
This implies that while taking a transition from state p to state q, the input symbol ‘b’ is consumed, and the top of
the stack ‘T’ is replaced by a new string ‘α’

Applications:

To construct automata that accepts language generated by Context-Free-Grammar.

A pushdown automaton is a way to implement a context-free grammar in a similar way we design DFA for a
regular grammar. A DFA can remember a finite amount of information, but a PDA can remember an infinite
amount of information.
Basically a pushdown automaton is −
"Finite state machine" + "a stack"
A pushdown automaton has three components −
 • an input tape,
• a control unit, and
• a stack with infinite size.
The stack head scans the top symbol of the stack.
A stack does two operations −
• Push − a new symbol is added at the top.
• Pop − the top symbol is read and removed.
A PDA may or may not read an input symbol, but it has to read the top of the stack in every transition.

Differences:

S.NO PUSHDOWN AUTOMATA FINITE AUTOMATA

For Type-2 grammar we can design Pushdown For Type-3 grammar we can design finite

1. automata. automata.

Non – Deterministic pushdown automata has Non-Deterministic Finite Automata has

more powerful than Deterministic pushdown same powers as in Deterministic Finite

2. automata. Automata.
 S.NO PUSHDOWN AUTOMATA FINITE AUTOMATA

Not every Non-Deterministic pushdown Every Non-Deterministic Finite

automata is transformed into its equivalent Automata is transformed into an

3. Deterministic pushdown Automata . equivalent Deterministic Finite Automata

Context free languages can be recognized by Regular languages can be recognized by

4. pushdown automata. finite automata.

Pushdown automata has the additional stack for Finite Automata doesn’t has any space to

5. storing long sequence of alphabets. store input alphabets.

It gives acceptance of input alphabhets by going It accepts the input alphabets by going up

6. up to empty stack and final states. to final states.

V
Definitions of Turing machines – Models – Computable languages and functions –Techniques for Turing machine
construction – Multi head and Multi tape Turing Machines – The Halting problem.