# How to create CFG for $L := \{x| \#_0(x) \text{ is even and } \#_1(x) \text{ is odd}\}$

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?

## 1 Answer

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.