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.

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?

share|improve this question

1 Answer 1

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

share|improve this answer

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.