1
$\begingroup$

Construct a context-free language for $L=\{w\in \{0,1\}^* \mid n_0(w)\not= 2n_1(w)\}$. Here $n_b(w)$ is the number of $b$'s in $w$.

I can construct a CFL in the case $n_0(w)=2n_1(w)$, but I have no idea how to construct it when they are not equal, considering that CFL is not closed under complement operation.

New contributor
My_Lulu is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$
2
$\begingroup$

Distinguish $n_0(w) < 2n_1(w)$ and $n_0(w) > 2n_1(w)$. That is, in your grammar for $n_0(w) = 2n_1(w)$ either generate extra $0$ or (in a separate half of the grammar) extra $1$.

$\endgroup$
  • $\begingroup$ Well, I wonder whether I can do it in the following way. Let $S$ represent strings $n_0(w)=2n_1(w)$, $A$ represent strings $n_0(w)>2n_1(w)$, $B$ represent strings $n_0(w)\ge 2n_1(w)$. Then we can have $A\rightarrow S0B$, $B\rightarrow S|A$. $\endgroup$ – My_Lulu Apr 15 at 9:36
  • $\begingroup$ Well, I just make it too complex. Thanks! $\endgroup$ – My_Lulu Apr 15 at 10:44

Your Answer

My_Lulu is a new contributor. Be nice, and check out our Code of Conduct.

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.