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.

The language $\mathcal{L}=\{a^n b^n c^n\;|\;n={1,2,3,4}\}$ is not context free from my point of view. Because no. of a's pushed in to stack is totally compensated by no of b's. popped. Please help me.

Also, please tell how to deduce its complement?

share|improve this question
add comment

2 Answers

$\mathcal L$ is finite, so of course it is regular. Its complement, $\overline{\mathcal{L}}$, is also regular. To see this, note that every word of $\mathcal L$ has length at most $12$. Let $$\mathcal L_0=\big\{w\in\{a,b,c\}^*\setminus\mathcal L:|w|\le 12\big\}\;,$$ and let $$\mathcal L_1=\big\{w\in\{a,b,c\}^*:|w|>12\big\}\;;$$ clearly $\overline{\mathcal{L}}=\mathcal L_0\cup\mathcal L_1$. $\mathcal L_0$ is finite and therefore regular, and it’s easy to see that $\mathcal L_1$ is regular as well: it’s trivial to design a regular grammar that generates $\mathcal L_1$ or a DFA that recognizes it. The union of two regular languages is regular, so $\overline{\mathcal{L}}$ is regular.

share|improve this answer
add comment

I made a mistake in my previous answer. First of all if we have $\mathcal{L}=\{a^kb^kc^k\;|\;k\in\mathbb{N}\}$ then $\mathcal{L}$ is NOT context free (see proof below). However if we bound $k\in\{1,2,3,4\}$ then your language can be enumerated extensionally like $$\mathcal{L}=\{abc, aabbcc, aaabbbccc, aaaabbbbcccc\}$$ and ACTUALLY IS therefore finite. We know that every finite language is regular which is a true subset of all context free languages. Considering the complement $\overline{\mathcal{L}}$ please refer to Brian's answer!


Proof for infinite language (not applicable on OP's example)

Let $\mathcal{L}:=\{a^kb^kc^k\;|\;k\in\mathbb{N}\}$ - we will show, that this language is not context free. If $\mathcal{L}$ would be context free there would be a Pumping Lemma number $n$ and we could split up every $z\in\mathcal{L}$ with $|z|\geq n$, especially $z=a^nb^nc^n$, and pump it up without ever getting out of the bounds of the language. A partition $z=uvwxy$ with $|vwx|\geq n$ implies that $vwx$ does not contain $a$'s and $c$'s. Without loss of generality we assume that $vwx$ does only contain $a$'s and $b$'s. With $vx\neq\epsilon$ we know that $vx$ has to have at least one $a$ and one $b$. Therefore we know that $$\#_a(uv^2wx^2y)>\#_c(uv^2wx^2y)$$ or $$\#_b(uv^2wx^2y)>\#_c(uv^2wx^2y).$$ (The $\#_x(w)$ operator denotes the number of occurences of $x$ in $w$.) Therefore $uv^2wx^2y\not\in\mathcal{L}$ and therefore $\mathcal L$ is not context free.

Hint: Furthermore ANY CFL G is NOT closed under complement. However, keep in mind that the complement of a non-CFL might me a CFL.

share|improve this answer
    
So its Complement is CFL? –  Sudhir Nov 13 '12 at 12:21
    
@Sudhir: Please have a look at my updated answer, I did a mistake before! –  Christian Ivicevic Nov 13 '12 at 13:02
    
$\{a^kb^kc^k:k\in\Bbb N\}$ isn’t the complement of the OP’s language $\mathcal L$. –  Brian M. Scott Nov 14 '12 at 13:46
    
@BrianM.Scott: I know that - my first answer was quite messy and everything is now... yeah. Thanks for the remark. –  Christian Ivicevic Nov 14 '12 at 15:40
    
@Chistrian: You’re welcome. (It’s still to have that proof handy, even if it isn’t actually needed here.) –  Brian M. Scott Nov 14 '12 at 21:08
add comment

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.