Pushdown Automata

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.

A stack does two operations −
  • Push − a new symbol is added at the top.
  • Pop − the top symbol is read and removed.

Pushdown Automata 


  •  A pushdown automaton (PDA) is a finite automaton equipped with a stack-based memory.
  •  Each transition 
  •  is based on the current input symbol and the top of the stack, 
  •  optionally pops the top of the stack, and 
  •  optionally pushes new symbols onto the stack. 
  •  Initially, the stack holds a special symbol Z0 that indicates the bottom of the stack. 

Our First PDA 

  •  Consider the language L = { w ∈ Σ* | w is a string of balanced digits } over Σ = { 0, 1 } 
  •  We can exploit the stack to our advantage: 
  •  Whenever we see a 0, push it onto the stack. 
  •  Whenever we see a 1, pop the corresponding 0 from the stack (or fail if not matched) 
  •  When input is consumed, if the stack is empty, accept.

Related Post in MCS-031 Solved Assignment

Discuss some real world problems, to which the techniques given below are applicable
(i) Divide & Conquer
(ii) Dynamic Programming
(iii) Greedy Approach

No comments

Powered by Blogger.