Log In
1 vote
how $a^nb^nc^n$ n>=1 is not CFL....??
in Theory of Computation
retagged by
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

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


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. :-)

Related questions

0 votes
0 answers
Consider a push down automata (PDA) below which runs over the input alphabet (a, b). It has the stack alphabet {z0, X}, where z0 is the bottom of stack marker. The set of states of PDA is {q0,q1} where q0 is the start state and rules of the PDA are, (The languare accepted by the grammar is)
asked Nov 30, 2018 in Theory of Computation rahuljai 238 views
0 votes
3 answers
S->AbaC A->BC B->b/epsilon C->D/epsilon D->d I want to know that will A contain epsilon as B and C both are null variables???(In Elimination of epsilon-production)
asked Nov 30, 2016 in Theory of Computation Anmol Verma 743 views
0 votes
0 answers
Consider the following CFG 'G' S--> aA/bSS/SS A--> aAb/bAa/AA/ε The language generated by G is: a)Set of all strings with atleast one 'a' b)Set of all strings with atleast two a's c)Set of all strings with atleast one more 'a' than number of b's d)None of these
asked Oct 18, 2018 in Theory of Computation Sambhrant Maurya 149 views
1 vote
2 answers
Consider Grammar G with the following characteristic- $A → ax$, where $A ∈ V$, $a ∈ T$, $x ∈ V^*$, and any pair $( A, a )$ occurs at most once in $P$. For example, $S → aA \mid aB...,$ is not a grammar of type $G$ because the pair $(S,a)$ occur in two productions. Which of ... a string w belonging to $L(G)$ ? $\mid w \mid^3$ $\mid w \mid$ $2^{\mid w \mid}$ Not a function of $\mid w \mid$ alone.
asked Feb 24, 2018 in Theory of Computation tarun_svbk 745 views