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.

| cite | improve this answer | |
$\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 | ๐œ€
| cite | improve this answer | |
$\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.