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?
$\begingroup$
$\endgroup$
2
-
$\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$– user2994783Commented Nov 25, 2019 at 17:13
-
1$\begingroup$ Looks like you've answered your question. $\endgroup$– André Souza LemosCommented Nov 25, 2019 at 17:23
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
