1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ @trolkura I assume that $|w|_1$ denotes the number of occurrences of the character $1$ in $w$. In any case, you must explain your notation. Homemade notation is no better than homemade terminology – we cannot understand questions written in a private language. Please edit your question to deal with the comments that have been made. $\endgroup$ – Hans Hüttel Nov 26 '16 at 16:13
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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 | 𝜀
$\endgroup$

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.