GATE CSE
First time here? Checkout the FAQ!
x
+2 votes
27 views

Either I dont understand PDA at all or this question is wrong or I am missing something very basic:

asked in Theory of Computation by (499 points)   | 27 views
state q0 denotes even no of a's and state q1 denotes odd no of a's.

Here we consider even no of a's then b and c should be equall.

at state q1 (c,b/$\epsilon$)  //pop 'b' for one 'c'.

at state q2 also same pop 'b' for one 'c'.

If a's are odd then no restriction on a's and b's.

at state q4 'b's are pushed into the stack.

when (c,b/cb)  push 'c' into stack or (c,b/b) skip 'b's.

same as q5 also.

Hence W=cb or b,X=$\epsilon$,Y=$\epsilon$,Z=cb or b

Please log in or register to answer this question.

Top Users Jan 2017
  1. Debashish Deka

    7050 Points

  2. Habibkhan

    4674 Points

  3. Vijay Thakur

    4224 Points

  4. saurabh rai

    4008 Points

  5. sudsho

    3960 Points

  6. Arjun

    3108 Points

  7. GateSet

    3088 Points

  8. santhoshdevulapally

    3004 Points

  9. Bikram

    2976 Points

  10. Sushant Gokhale

    2744 Points

Monthly Topper: Rs. 500 gift card

18,810 questions
23,779 answers
51,413 comments
20,128 users