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$.

  • $\begingroup$ The language $L_3$ is regular. $\endgroup$ – Yuval Filmus Sep 17 '19 at 11:53

$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$.

  • 1
    $\begingroup$ For L3, notice you could not have an NFA with a cycle to eat as much input as possible, and then two branches to accepting states (1010 and 0101). The idea would be to accept all inputs ending in those two patterns (5 and 10, respectively)—the problem being that, in base 2, this sort of divisibility testing doesnt work like it does in base 10 $\endgroup$ – D. Ben Knoble Sep 17 '19 at 12:25
  • $\begingroup$ Exactly. Following the same approach as above for a multiple of 2 would result in a formula where the contribution of almost all bits is 0 and only the least significant bits count. For multiples of 5 all bits have to be taken into account. $\endgroup$ – Steven Sep 17 '19 at 12:54

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.