DEV Community

Cover image for PDA- Pushdown Automata
Muhammad Sajjad Saddique
Muhammad Sajjad Saddique

Posted on

PDA- Pushdown Automata

Pushdown automata is a finite automata with extra memory called stack which helps pushdown automata to recognize Context Free Languages.

A pushdown autimaton 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 autimaton is-
"Finite state machine" + "a stack"
A pushdown autimaton has three components-

  • an input tape,

  • a control unit, and

  • a stack with infinite size.

A pushdown automata (PDA) can be defined as:

Q:is a set of states
q0:is the initial state
Z: is the initial pushdown symbol
F: is the set of final states etc.

Discussion (0)