GATE CSE
First time here? Checkout the FAQ!
x
0 votes
181 views
how $a^nb^nc^n$ n>=1 is not CFL....??
asked in Theory of Computation by Active (1.3k points)  
retagged by | 181 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}$...???
Subset of a context free language may or may not be context free.

a^n n is a natural number is context free

a^n where n is a prime number is not.

Though latter is the subset of the former. :-)


Top Users Jul 2017
  1. Bikram

    3946 Points

  2. manu00x

    2464 Points

  3. Debashish Deka

    1842 Points

  4. joshi_nitish

    1650 Points

  5. Arjun

    1268 Points

  6. Hemant Parihar

    1184 Points

  7. Arnab Bhadra

    1100 Points

  8. Shubhanshu

    1052 Points

  9. Ahwan

    900 Points

  10. rahul sharma 5

    692 Points


24,016 questions
30,946 answers
70,303 comments
29,333 users