Theory Of Computation (2160704)

BE | Semester-7   Winter-2018 | 27/11/2018

Q4) (c) 

Define PDA. Describe the pushdown automata for language {0

  • A pushdown Automata is essentially a finite Automata with a stack data structure.
  • A PDA can write an unbounded no. of symbols on the stack and read these symbols later.
  • Writing a symbol on to the stack is called “PUSH” operation.
  • Removing a symbol off the stack is called “POP” operation.

Use 0 And 1 Instead Of a and b in this example

Move No State i/p Stack Symbol Move
1 q0 ^ Z0 (q2,z0)
2 q0 a Z0 (q0,aZ0)
3 q0 a a (q0,aa)
4 q0 b a (q1,^)
5 q1 b a (q1,^)
6 q1 ^ Z0 (q2,Z0)
  • String:aaabbb
Resulting State Unread i/p Stack
q0 aaabbb Z0
q0 aabbb aZ0
q0 abbb aaZ0
q0 bbb aaaZ0
q1 bb aaZ0
q1 b aZ0
q1 ^ Z0
q2 ^ Z0
accepted
PDA accepting Number of a’s and b’s are same
(Figure: PDA accepting Number of a’s and b’s are same)

Questions

Go to Question Paper