Pushdown Automata Tutorial Notes Study Material with Examples
What is Pushdown Automata (PDA)
A Pushdown Automata (PDA) is essentially an NFA with a Stack. A PDA is inherently non-deterministic. To handle a language like {an bn | n ≥ 0}, the machine needs to remember of a’s and b’s. To do this, we use a stack. So, a PDA is a finite automaton with a stack. A stack is a data structure that can contain an number of elements but for which only the top element may be accessed.
Definition of PDA
A pushdown Automaton (PDA) is defined as 7-tuple.
M=(Q, Ʃ, г, δ, q0, Z, F)
Where Q is a finite set of states
Ʃ is the input set of states
Г is the stack alphabet
δ is the transition function which maps
()
q0 is the start state and Ɛ denotes the empty string.
q0 ϵ Q is start state.
Z ϵ Г is the initial stack symbol
F intersection Q is the set of final or accepting states.
Acceptance of PDA
Tape is divided into finitely many cells. Each cells contains a symbol in an alphabet Ʃ. The stack head always scans the top symbol of the stack as shown in figure.
It performs two basic operations
Push and a new symbol at the top.
Pop read and remove the top symbol.
δ(q, a, v) =(p, u)
It means that if the tape head reads input a, the stack head read v and the finite control in state q, then one of the possible moves is that the next state is p, v is replaced by u at stack and the tape head moves on cell to the right.
δ(q, ^, v) =(p, u)
It means that this is a ^-move (null move)
δ(q, a, ^) =(p, u)
It means that a push operation performs on stack.
δ(q, a, v) =(p, ^)
It means that a pop operation performs on stack.
Key Points
- In computer science, a pushdown automata is a type of automata that employs stack.
- The PDA is used in theories about what can be computer by machine.
- PDA is more Capable than a finite-state machine but less capable than a turning machine.
Non-deterministic PDA
Like NFA, Non-deterministic PDA (NPDA) has number is choices for its inputs. An NPDA accepts an inputs, if sequence of choices leads to some final state or causes PDA to empty its stack.
Deterministic PDA
Deterministic PDA (DPDA) is a pushdown automata whose action is an situation is fully determined rather than facing a choice between multiple alternative actions. DPDAs cannot handle language of Grammars with ambiguity. A deterministic context-free language is a language recognized by some deterministic pushdown automata.
Following languages are DCFLs
- L = { anbn : n ≥ 0}
- L = { an cb2n : n ≥ 0}
- L = { ωcωR : ω ϵ (a+b)* but not L= (ωωR : (a+b)*}
Key points
- For any context-free language L these exist an NPDA is such form L =L(m).
- If L=L(m) for some NPDA m then L is a context-free Language.
- The family of context-free language is closed under union concatenation and star closure (L*) . Means for once input b is arrived there should be state change to ensure that. Only input b is acceptable.
- To ensure that a is equal to b we will push all a to stack and after reading b we will be pop one a with one b.
Parsing Tutorial Notes Study Material with Examples in Handbook Series
Follow Us on Social Platforms to get Updated : twiter, facebook, Google Plus
Learn Parsing in Handbook Series: Click here