GATE CSE
First time here? Checkout the FAQ!
x
+1 vote
212 views
how $a^nb^nc^n$ n>=1 is not CFL....??
asked in Theory of Computation by Active (1.4k points)  
retagged by | 212 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

+1 vote

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 Sep 2017
  1. Habibkhan

    8312 Points

  2. Warrior

    2862 Points

  3. rishu_darkshadow

    2796 Points

  4. Arjun

    2766 Points

  5. A_i_$_h

    2526 Points

  6. manu00x

    2094 Points

  7. nikunj

    1980 Points

  8. Bikram

    1874 Points

  9. makhdoom ghaya

    1810 Points

  10. SiddharthMahapatra

    1718 Points


26,281 questions
33,842 answers
80,382 comments
31,192 users