GATE CSE
First time here? Checkout the FAQ!
x
+1 vote
379 views

Which solution is correct one?

I wish I solved it correctly (sol1)

asked in Theory of Computation by Boss (6.8k points)  
retagged by | 379 views
You are correct I think

2 Answers

+3 votes

One Approach 

1 .If you are in state Qo and a is the input and Zo is on top of the stack then push aa instead of single a

2 .If you are in state Qo and a is the input and a is on top of the stack then push aa instead of single a

3 .If you are in state Qo and b is the input and a is on top  of the stack then get the state Q1 and  pop a 

Pop one a for one b because we have already pushed 2 aa's instead of one a .

As long as you are in state Q2 keep on poping off  a for every b.

Once the string is empty you can accept it

Second Approach

instead of pushing 2 a's push only one a in state Qo and once you see a "b" make a transition in state Q2 and for every one "a" pop off 2 b's.

(for first b don't do anything and in case of second b pop off a) Do it alternatively 

Both approach's  work well....

answered by Veteran (42.9k points)  
edited by
0 votes

Solution:

Step1:Push 'aa'  instead 'a', whenever 'a' comes on q0(Start) .

Step2: Pop one 'a' whenever 'b' comes and change the state from q0 to q1.

Step3: For all remaining 'b' repeat the same procedure staying on q1.

Step4: When ^ comes and if TOS is Z0, than go to the accept state(End).

answered by Loyal (2.8k points)  


Top Users Sep 2017
  1. Habibkhan

    7096 Points

  2. Warrior

    2574 Points

  3. Arjun

    2412 Points

  4. rishu_darkshadow

    2402 Points

  5. A_i_$_h

    2204 Points

  6. nikunj

    1980 Points

  7. manu00x

    1846 Points

  8. makhdoom ghaya

    1760 Points

  9. Bikram

    1744 Points

  10. SiddharthMahapatra

    1718 Points


26,115 questions
33,691 answers
79,844 comments
31,098 users