3
$\begingroup$

I need help solving this question:

Is $L = \{ w \in \{a,b,c\}^* \mid n_a(w) = n_b(w) = 2n_c(w)\}$ a context-free language? That is the number of $a$'s equal the number of $b$'s equal twice the number of $c$'s in the string $w$.

First, I think that the language is context-free, but i'm having trouble finding a context free grammar to prove it.

So far I have:

\begin{align} S &\to SASBS \mid SBSAS \mid λ \\ A &\to a \\ B &\to b \\ \end{align}

I'm not sure how to get twice the number of $c$'s, could someone please show me/correct me?

$\endgroup$
4
$\begingroup$

Hint: The language is (unfortunately) not context free. Recall the Pumping Lemma for context free languages, and suppose that $p$ is the pumping length of $L$. Now consider the string $w = \mathtt{a}^{2p} \mathtt{b}^{2p} \mathtt{c}^p$. (Note that no substring of $w$ of length $\leq p$ can contain $\mathtt{a}$s, $\mathtt{b}$s and $\mathtt{c}$s.)

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