1
$\begingroup$

I have got following question:

Determine whether the following language is context free or not: $$L = \{ w \in \{a,b,c\}^*: n_a (w) = n_b (w) = 2n_c (w)\}. $$

What is the meaning of $2n_c$ in the above question?

$\endgroup$
  • $\begingroup$ $2n_c$ = twice the number of 'c's. This means that number of c's is twice the number of 'a's and b's. Is this correct? If this is correct then this means that we would push 'a' onto the stack, push 'b' on to the stack and then we would pop. So number of 'c's is greater than the combined value of 'a's and 'b's. So stack would be empty and the string would be accepted. $\endgroup$ – user2994783 Nov 25 '19 at 17:13
  • 1
    $\begingroup$ Looks like you've answered your question. $\endgroup$ – André Souza Lemos Nov 25 '19 at 17:23
1
$\begingroup$

This language is not CFL.

Consider the language $L \cap a^*b^*c^*$ . Assume that $L$ is CFL, now, as $ a^*b^*c^*$ is regular and CFL are closed under intersection with regular languages, $L \cap a^*b^*c^*$ would be CFL. But $L \cap a^*b^*c^* = a^nb^nc^{2n}$, which is not context free (The proof is similar to this). Hence the contradiction!

Thus the given language is not CFL.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.