A context-free grammar for a language of strings with occurrence properties?

Question

Creating a context-free grammar for the language

$L_1 = \{ 0^{n} 1 ^{m} \mid m,n \in \mathbb{N} \wedge m \equiv n \mod 3\}$

is quite easy. A grammar is

$$ S \rightarrow \epsilon \mid 0A $$ $$ A \rightarrow 1 \mid 0B $$ $$ B \rightarrow 11 \mid 0S $$

But I am now trying to create a context-free grammar for

$L_2 = \{ w \in \{0 ,1 \}^{*} \mid |w|_1 \equiv |w|_0 \mod 3 \}$

Here, $|w|_1$ denotes the number of occurrences of the character $1$ in the string $w$, and $|w|_0$ is defined similarly.

How does one construct a context-free grammar? All my attempts have lead to completely wrong results. At the moment I am stuck.

Answer 1

Both $L_1$ and $L_2$ are regular languages. To construct a context-free grammar for them, you can first construct a DFA or NFA accepting them, and then convert it to a regular grammar.

Answer 2

Assuming you want the strings where m is the number of digits 1 in the string, n is the number of digits 0 in the string, and m = n modulo 3.

Have symbols that derive the following:

A -> "string where m = n modulo 3"
B -> "string where m = (n + 1) modulo 3"
C -> "string where m = (n + 2) modulo 3"
D -> "string where (m+1) = n modulo 3"
E -> "string where (m+1) = (n + 1) modulo 3"
F -> "string where (m+1) = (n + 2) modulo 3"
G -> "string where (m+2) = n modulo 3"
H -> "string where (m+2) = (n + 1) modulo 3"
J -> "string where (m+2) = (n + 2) modulo 3"

Now it's simple:

S -> A
A -> 0B | 1D | 𝜀
B -> 0C | 1E
C -> 0A | 1F
D -> 0E | 1G
E -> 0F | 1H | 𝜀
F -> 0D | 1J
G -> 0H
H -> 0J
J -> 0G | 𝜀