Q29

MCQ2 marks, −0.5

If $s$ is a string over $(0+1)^*$ then let $n_0(s)$ denote the number of $0$ ’s in $s$ and $n_1(s)$ the number of $1$ ’s in $s$ . Which one of the following languages is not regular?

(A)

$L=\left \{ s\in (0+1)^* \mid n_{0}(s) \text{ is a 3-digit prime } \right \}$

(B)

$L=\left\{ s \in (0+1)^* \mid \text{ for every prefix s' of s,} \mid n_{0}(s')-n_{1}(s') \mid \leq 2 \right \}$

(C)

$L=\left \{ s\in (0+1)^*\mid n_{0}(s)-n_{1}(s)\mid \leq 4 \right \}$

(D)

$L=\left \{ s\in (0+1)^*\mid n_{0}(s) \mod 7=n_{1}(s) \mod 5=0 \right \}$

Loading…