0

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

DanielY
  • 979

3 Answers3

4

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.

Brian M. Scott
  • 616,228
  • 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
  • @user1067083: Ah, I see; no, I can edit it even after it’s accepted. I’ve been thinking about it, but so far I’ve not managed to prove it without using closure under inverse homomorphisms. Of course if $L$ is a CFL, so is $L'={a^{2n}b^{2n}c^{2n}:n\ge 0}$, but the most elementary non-pumping lemma argument that I can find that $L'$ isn’t a CFL is to show how to modify a PDA that accepts $L'$ to get one that accepts ${a^nb^nc^n:n\ge 0}$. – Brian M. Scott Dec 29 '12 at 19:57
  • OK I'll go with your solution and hope for the best. thanks alot :) – DanielY Dec 29 '12 at 21:32
  • @user1067083: You’re welcome. (And if I have any brilliant ideas, I’ll post them, but don’t hold your breath! :-)) – Brian M. Scott Dec 29 '12 at 21:33
  • You've done enough as it is, thanks alot Mr. Brian – DanielY Dec 29 '12 at 21:36
0

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!

Mithlesh Upadhyay
  • 4,787
DanielY
  • 979
  • 1
    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 03 '13 at 18:48
  • 1
    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 03 '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 03 '13 at 21:08
-3

$$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.

AugSB
  • 5,007
rajesh puppala
  • 1