Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

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

2 Answers 2

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.

share|improve this answer
    
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? –  DanielY Dec 28 '12 at 12:33
1  
@user1067083: Do you know that context-free languages are closed under homomorphisms? –  Brian M. Scott Dec 28 '12 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 –  DanielY Dec 28 '12 at 13:04
    
And the reason for the downvote is? If there is a genuine error, I’d like to know about it. –  Brian M. Scott Dec 28 '12 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? –  DanielY Dec 29 '12 at 16:01
up vote 0 down vote accepted

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!

share|improve this answer
    
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. –  Brian M. Scott Jan 3 '13 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! –  DanielY Jan 3 '13 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 –  DanielY Jan 3 '13 at 21:08

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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