# is this language context-free? a tricky one

Is this language context-free?

$$L = \{a^nb^nc^{2n} \mid n \ge 0\}$$

It's tricky in my opinion because I know that $a^nb^nc^n$ is not context-free, but can I determine from this that $L$ is not context-free, too?

EDIT: I can use these closures: all the closures of regular languages, the closure of intersection of regular language with a context-free language, and closure under homorphishms

• From your reply to Brian's answers, it seems you are restricted to particular techniques for the exercise, what are they? Dec 28, 2012 at 12:44
• see my comment to Brian's answer Dec 28, 2012 at 13:02
• @user1067083: That sort of important restrictions should be edited into the question, not hidden in comments to an answer. Dec 28, 2012 at 13:22
• you're right. Thanks Dec 28, 2012 at 13:33

It is not context-free. You can show this using the pumping lemma for context-free languages; the proof is very similar to the one for the language $\{a^nb^nc^n:n>0\}$, which is given in the linked article.

Added: Since you’re restricted to closure properties, perhaps the easiest argument is to use closure under inverse homomorphisms, using the homomorphism $h$ such that $h(a)=a$, $h(b)=b$, and $h(c)=cc$. If $L$ were context-free, $\{a^nb^nc^n:n\ge 0\}$ would also be context-free.

• Thanks Brian for you quick answer. Unfortunately I'm not allowed to use the pumping lemma to show this, only by closures. Do you have any idea for me? Dec 28, 2012 at 12:33
• @user1067083: Do you know that context-free languages are closed under homomorphisms? Dec 28, 2012 at 12:42
• I can use these closures: all the closures of regular languages, the closure of intersection of regular language with a context-free language, and closure under homorphishms Dec 28, 2012 at 13:04
• And the reason for the downvote is? If there is a genuine error, I’d like to know about it. Dec 28, 2012 at 14:45
• I just thought you won't be able to edit it if it's voted on...vote is back! And if I may drive you a bit more crazy, how can I prove this with closure under homomorphism, not inverse? Dec 29, 2012 at 16:01

So at the first time I end up answering my own question. Hope that I will get more chances such as those at the future to help others

Here it is:

Let's consider that this language IS context-free. We'll define a regular function F such that:

$F(c) = c' + c$

$F(b) = b$

$F(a) = a$

So $F(L)$ is also context-free from closure to homomorphisms.

Now consider the language $L' = F(L) ∩ \{a^*b^*(cc')^*\}$, that's also context-free due to closure under intersection with regular.

Finally, define a function G such that:

$G(c') = \epsilon$

$G(a) = a$,

$G(b) = b$,

$G(c) = c$

So $G(L') = \{a^nb^nc^n\}$ is context-free. But we know it's not - BAM!

Therefore, $L$ is not context-free!

• I’m going to assume that you meant $F(c)$ to be $cc'$, to match the regular expression later in the answer. Then $F[L]=\{a^nb^n(cc')^{2n}:n\ge 0\}$, and $L'=F[L]$: the intersection with $a^*b^*(cc')^*$ doesn’t do anthing, since $F[L]$ is already a subset of that language. Finally, $G[L']$ is just $L$ all over again, so I’m afraid that this doesn’t work. Jan 3, 2013 at 18:48
• no no sir, I meant c + c', that means c can be either c or c'! that's the language of the words that there are a's, b's, and then c or c' in arbitrary order...look thoroughly, things work! Jan 3, 2013 at 21:06
• @BrianM.Scott since you're already here, is there any possibilty you give me an extra explaination to my question I've already deleted? with the prefixes of a context-free language that is also context-free? I can't get my proof properly...Just give me a proper way that you can help me from and I'll do it Jan 3, 2013 at 21:08

$$L=\{a^nb^nc^2n/n\ge1\}$$ is not context free but it is context sensitive language. here we can write like below and think it is cfl $a^n b^n c^n c^n$ no of $a$'s plus no of $b$'s is equal or not to no of $c$'s of twice of $a$'s and b's it should be possible bcz we can maintain a count between no of $b$'s and $c$'s then $a$'s and $c$'s but it is not correct . reason is we are maintaining count between no of $a$'s plus no of $b$'s but not no of $a$'s equal to no of $b$'s hence it is cfl.

• Please make an honest attempt at fixing the formatting of your post. Jun 23, 2016 at 12:35