Create an CFG for all strings over {0, 1} that have the an even number of 0’s and an odd number of 1’s.

Also, I have a hint HINT: It may be easier to come up with 4 CFGs – even 0’s, even 1’s, odd 0’s odd 1’s, even 0’s odd 1’s, odd 1’s, even 0’s – and combine them ...

But I can't understand how it works

Who can help?


Let us define 4 non-terminals $X_{00}, X_{01}, X_{10}, X_{11}$ and the start variable $S$. The rules are as follow: \begin{align} S &\rightarrow X_{00},\\ X_{01}&\rightarrow \epsilon,\\ X_{00}&\rightarrow 0X_{10},\\ X_{00}&\rightarrow 1X_{10},\\ X_{01}&\rightarrow 0X_{11},\\ X_{01}&\rightarrow 1X_{00},\\ X_{10}&\rightarrow 0X_{00},\\ X_{10}&\rightarrow 1X_{11},\\ X_{11}&\rightarrow 0X_{01},\\ X_{11}&\rightarrow 1X_{10},\\ \end{align} where the first index tells the parity of the number of zeros and the second one the parity of the count of ones.

Try to prove the correctness as an exercise.

| cite | improve this answer | |

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.