The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+1 vote
L={a^n,b^n,c^m / n>m}

we have to compare n and m everywhere I know till we reach b there will be nothing in the stack BUT generally we can make this language if possible

suppose when we are putting one a into the stack suppose we put Two a's on behalf of one a then the no'of a's 2*n into the stack and the we pop one a for one b after completing allb's still there will be n number of a's will be remaining into the stack then we can compare number of a's and number of c's if and one a or more than one a is remaining in the stack then we can accept the string otherwise we can reject the string

I'm asking this question because in one of the video for the question we were  taking two a's on behalf of one .......
asked in Theory of Computation by (275 points) | 57 views
a and b are equal ,then how can you push 2 'a' for every b ,for each 'b' u have to pop  'a ' or for each 2 'b' you have to pop 2 b .you have to push n pop same because both are same.

This is simply csl , there needs of two stack

No, it will not work as you will not be able to compare the equality of a and b .. by your logic a^2b^1c^1 will be accepted.. which should not be the case.

It's a CSL.

1 Answer

0 votes
This is simply CSL, you can not push a's for one b. You have to push 1a for 1b and once you are done with b’s you got stuck on a because in PDA you simply can not go left or save the number of a's.

So finally it is CSL and can be accepted by LBA because of the feature that you can move to either left or right as per the situation. That's why we say that LBA can accept anything.
answered by Active (1.5k points)

Related questions

0 votes
1 answer
+2 votes
1 answer

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

46,769 questions
51,221 answers
66,581 users