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

0
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...?
1

@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'.

0
isn't $L_{1}$ a subset of $L_{2}$...???
1
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
1
179 views
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 179 views
0 votes
3 answers
2
307 views
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 307 views
0 votes
0 answers
3
105 views
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 105 views
1 vote
2 answers
4
438 views
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 438 views
...