1 votes 1 votes how $a^nb^nc^n$ n>=1 is not CFL....?? Theory of Computation theory-of-computation context-free-language grammar context-free-grammar pushdown-automata + – Anmol Verma asked Dec 2, 2016 retagged Jul 4, 2017 by Arjun Anmol Verma 872 views answer comment Share Follow See 1 comment See all 1 1 comment reply mcjoshi commented Dec 2, 2016 reply Follow Share 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 votes 1 votes Please log in or register to add a comment.
1 votes 1 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 RAJESHWAR YADAV answered Dec 2, 2016 RAJESHWAR YADAV comment Share Follow See all 4 Comments See all 4 4 Comments reply Anmol Verma commented Dec 2, 2016 reply Follow Share 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...? 0 votes 0 votes anonymous commented Dec 2, 2016 reply Follow Share @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'. 1 votes 1 votes Anmol Verma commented Dec 2, 2016 reply Follow Share isn't $L_{1}$ a subset of $L_{2}$...??? 0 votes 0 votes Karan Saini commented Jul 8, 2017 reply Follow Share 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. :-) 1 votes 1 votes Please log in or register to add a comment.