GATE CSE
First time here? Checkout the FAQ!
x
0 votes
114 views
how $a^nb^nc^n$ n>=1 is not CFL....??
asked in Theory of Computation by Active (1.2k points)   | 114 views
A CFL is accepted by a stack, means using push and pop operations only, the every string of language should be accepted. Can you accept the above language using stack only?

For string $aaabbb$, you can use a stack saying Push all a's, then Pop() for every b in input string. and if we find our stack empty after seeing all b's, we can say Yeah!! string got accepted.

Can you do something similar to this for $aaabbbccc$?

1 Answer

0 votes

we can not compare equal no. of  a ,b and c in stack 

we can only compare two equal no. of symbol i.e. anbn

answered by Active (1.3k points)  
cant we leave 'c' uncompared.....

there is a question L={$a^{n}b^{n}c^{m}$, n,m>=1}

this language is a context free as we leave 'c' uncompared here...?

@Anmol Verma  language in question i.e L1={anbncn,n>=1} is different from

L2={an,bn,cm,n,m>=1}.

in L1, we need 2 stacks because we have equal no. of a,b & c While in L2,we don't need equal no of a,b,c (though equal no of a & b but not c). Here, we can leave c 'Uncomapred'.

 

isn't $L_{1}$ a subset of $L_{2}$...???


Top Users Mar 2017
  1. rude

    4758 Points

  2. sh!va

    3014 Points

  3. Rahul Jain25

    2830 Points

  4. Kapil

    2636 Points

  5. Debashish Deka

    2442 Points

  6. 2018

    1514 Points

  7. Vignesh Sekar

    1416 Points

  8. Akriti sood

    1298 Points

  9. Bikram

    1286 Points

  10. Sanjay Sharma

    1076 Points

Monthly Topper: Rs. 500 gift card

21,471 questions
26,802 answers
61,041 comments
23,037 users