Examples of Regular, Context-free and Context-sensitive languages

Question

Assume the languages:

$$ a) \, L_1 = \{ w \in \{b,c \}^* | \, w \, \text{contains 'bbc' as substring} \} $$ $$ b)\, L_2 = \{ 1^k 0^m 1^m | k,m \in \mathbb{N} \} $$ $$ c)\,L_3 = \{ w \in {0,1}^* | \, w \, \text{is a multiple of 5 (binary system) }\} $$ $$ d)\,L_4 = \{ d^k e^m f^k | k,m \in \mathbb{N}, \, k < m\} $$

$L_1$: Since we could build an NFA which accepts its strings, it's regular.

$L_2$: Using a single stack or PDA, by pushing $0$ to the stack for every $0$ in the string and then poping from the stack for every $1$ (after the $0$s) in the string, we can determine whether the string is in the language if the stack ends up empty. Thus, $L_2$ is context-free.

$L_4$: Same as above, but this time we need $2$ stacks (LBA). Push $0$s in the first stack for every $d$, push $1$s in the second stack for every $e$ and then pop from the two stacks for every $f$. If the first stack ends up empty and second ends up non-empty, then the string belongs to the language. Thus, $L_4$ is context-sensitive.

Are the above conclusions correct? If so, please provide me with a hint for the classification of $L_3$.

Answer 1

$L_1$, $L_2$ and $L_4$ are correct (notice that you are not showing that $L_2$ is not regular and $L_4$ is not context-free, which can be done using the appropriate version of the pumping lemma).

As far as $L_3$ is concerned, let $x$ be the number that is encoded in binary and call $x_i$ its $i$-th least significant bit, indexed from $0$. Then, counting modulo 5, we have:

$\displaystyle x = \sum_{i=0}^\infty x_i 2^i = \sum_{i=0,4,8..} x_i + 2 \sum_{i=1,5,9..} x_i + 4 \sum_{i=2,6,10..} x_i + 3 \sum_{i=3,7,11..} x_i$.

I.e., the least significant binary digit contributes $1$ to $x \bmod 5$, the next one contributes 2, then 4, 3, 1, 2, 4, 3, ... and this pattern repeats.

This means that you can create a DFA that recognizes $L_3^R$ (and hence $L_3$) using at most 20 states, namely $\langle i,j \rangle$ where $i \in \{0,1,2,3\}$ is the index, modulo 4, of the next character in the string, and $j \in \{0,1,2,3,4\}$ is the partial sum, modulo $5$, of the contributions of binary digits seen so far.

If the next bit is $0$ then: $\langle i,j \rangle \to \langle i+1 \pmod 5, j \rangle$.

If the next bit is $1$ then $\langle i,j \rangle \to \langle i+1 \pmod 5, j+ 2^i \pmod 5\rangle$. Writing this down explicitly:

• $\langle 0,j \rangle \to \langle 1, j+1 \pmod 5\rangle$;
• $\langle 1,j \rangle \to \langle 2, j+2 \pmod 5\rangle$;
• $\langle 2,j \rangle \to \langle 3, j+4 \pmod 5\rangle$;
• $\langle 3,j \rangle \to \langle 0, j+3 \pmod 5\rangle$.

The initial state is $\langle 0, 0 \rangle$ and the final states are all the ones of the form $\langle i, 0 \rangle$.