How to I generate a CFG from the language that have even length and have at most two 0’s
L3 = {w ∈ {0, 1} ∗ | w is even length, 0<=2 }
I feel stuck on meeting the criteria of maximum two 0s
My attempt so far is
S -> 0H0H | 00H
H -> 1H1H | 11A | e
Many thank guys
On
Let $S$ represent the state where you haven't seen any zeroes. Let $T$ represent the state where you have seen exactly one zero, and let $U$ represent the state where you've seen two zeroes.
Then a grammar for your language is:
\begin{align*} S &\mapsto \epsilon \;|\; 11 S \;|\; 01 T \;|\; 10T\;|\;00U\\ T &\mapsto \epsilon\;|\;11T\;|\;01U\;|\;10U\\ U &\mapsto \epsilon \;|\;11U \end{align*}
Intuitively, this grammar reads two characters at a time from left to right, transitioning into the appropriate state based on how many zeroes it reads.
There are certainly more elegant context-free grammars for this language, but hopefully this one is usefully readable. You can tell that this language is not only context-free, but moreover regular because all the productions have terminal symbols before nonterminal symbols.
Word with at most two zeroes has either $0$, $1$ or $2$ zeroes. If it has $0$ zeroes, it's just words of $1$s of even length.
If it has $1$ zero, it's of form $a0b$ where both $a$ and $b$ consist of $1$s, and either $|a|$ is odd and $|b|$ is even or vice versa.
If it has $2$ zeroes, it's of form $a0b0c$, where $a, b, c$ consist of $1$s, and there are some (not big) number of variants of parities of their lengths.
Given this, we can write grammar for our language like $E \to \Lambda\ |\ 1O$, $O \to 1E$, $S \to E\ |\ E0O\ |\ O0E\ |\ E0E0E\ |\ \ldots$ - can you find the rest variants?
(actually, this language is not only context-free, but even regular - just build automatas for checking number of $0$s and parity and take intersection)