The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+1 vote
461 views

Which solution is correct one?

I wish I solved it correctly (sol1)

asked in Theory of Computation by Boss (7.9k points)
retagged by | 461 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 (43.4k 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 (3.2k points)


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

28,946 questions
36,791 answers
91,047 comments
34,688 users