0
$\begingroup$

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
    From your reply to Brian's answers, it seems you are restricted to particular techniques for the exercise, what are they?2012-12-28
  • 0
    see my comment to Brian's answer2012-12-28
  • 2
    @user1067083: That sort of important restrictions should be **edited into the question**, not hidden in comments to an answer.2012-12-28
  • 0
    you're right. Thanks2012-12-28

3 Answers 3

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

  • 4
    Please make an honest attempt at fixing the formatting of your post.2016-06-23
3

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.

  • 0
    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?2012-12-28
  • 1
    @user1067083: Do you know that context-free languages are closed under homomorphisms?2012-12-28
  • 0
    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 homorphishms2012-12-28
  • 0
    And the reason for the downvote is? If there is a genuine error, I’d like to know about it.2012-12-28
  • 0
    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?2012-12-29
  • 0
    @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\}$.2012-12-29
  • 0
    OK I'll go with your solution and hope for the best. thanks alot :)2012-12-29
  • 0
    @user1067083: You’re welcome. (And if I have any brilliant ideas, I’ll post them, but don’t hold your breath! :-))2012-12-29
  • 0
    You've done enough as it is, thanks alot Mr. Brian2012-12-29
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!

  • 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.2013-01-03
  • 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!2013-01-03
  • 0
    @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 it2013-01-03