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

$\endgroup$
4
  • 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, 2012 at 12:44
  • $\begingroup$ see my comment to Brian's answer $\endgroup$
    – DanielY
    Dec 28, 2012 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$
    – hmakholm left over Monica
    Dec 28, 2012 at 13:22
  • $\begingroup$ you're right. Thanks $\endgroup$
    – DanielY
    Dec 28, 2012 at 13:33

3 Answers 3

Reset to default
4
$\begingroup$

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.

$\endgroup$
9
  • $\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, 2012 at 12:33
  • 1
    $\begingroup$ @user1067083: Do you know that context-free languages are closed under homomorphisms? $\endgroup$
    – Brian M. Scott
    Dec 28, 2012 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, 2012 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, 2012 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, 2012 at 16:01
0
$\begingroup$

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!

$\endgroup$
3
  • 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, 2013 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, 2013 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, 2013 at 21:08
-3
$\begingroup$

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

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .