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?

Thanks in advance

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

  • 2
    $\begingroup$ From your reply to Brian's answers, it seems you are restricted to particular techniques for the exercise, what are they? $\endgroup$ – Luke Mathieson Dec 28 '12 at 12:44
  • $\begingroup$ see my comment to Brian's answer $\endgroup$ – DanielY Dec 28 '12 at 13:02
  • 2
    $\begingroup$ @user1067083: That sort of important restrictions should be edited into the question, not hidden in comments to an answer. $\endgroup$ – Henning Makholm Dec 28 '12 at 13:22
  • $\begingroup$ you're right. Thanks $\endgroup$ – DanielY Dec 28 '12 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.

  • $\begingroup$ 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? $\endgroup$ – DanielY Dec 28 '12 at 12:33
  • 1
    $\begingroup$ @user1067083: Do you know that context-free languages are closed under homomorphisms? $\endgroup$ – Brian M. Scott Dec 28 '12 at 12:42
  • $\begingroup$ 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 $\endgroup$ – DanielY Dec 28 '12 at 13:04
  • $\begingroup$ And the reason for the downvote is? If there is a genuine error, I’d like to know about it. $\endgroup$ – Brian M. Scott Dec 28 '12 at 14:45
  • $\begingroup$ 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? $\endgroup$ – DanielY Dec 29 '12 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!

  • 1
    $\begingroup$ 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. $\endgroup$ – Brian M. Scott Jan 3 '13 at 18:48
  • 1
    $\begingroup$ 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! $\endgroup$ – DanielY Jan 3 '13 at 21:06
  • $\begingroup$ @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 $\endgroup$ – DanielY Jan 3 '13 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.

  • 4
    $\begingroup$ Please make an honest attempt at fixing the formatting of your post. $\endgroup$ – Mårten W Jun 23 '16 at 12:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.