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

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

  • 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!

  • 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