-
If s is a string over (0 + 1)* then let n0 (s) denotes the number of 0's in s and n1 (s) the number of 1's in s. Which one of the following languages is not regular?
-
- L = {s ∈ (0 + 1)* | n0 (s) is a 3-digit prime}
- L = {s ∈ (0 + 1)* | for every prefix s' of s, | n0 (s') - n1 (s') ≤ 2}
- L = {s ∈ (0 + 1)* | n0 (s) - n1 (s)| ≤ 4
- L = {s ∈ (0 + 1)* | n0 (s) mod 7 = n1 (s) mod 5 = 0}
- L = {s ∈ (0 + 1)* | n0 (s) is a 3-digit prime}
Correct Option: C
Option (a), (b) & (d) can be accepted by DFA, & there is no linear relationship between the no. of 0' s &1' s in the string but in (c)n0 (S) - n1 (S) <= 4 can't be accepted by DFA, we require a PDA. Hence it is not regular.
