Q. If s is a string over (0 + 1)* then let n0 (s) denote the number of 0’s in s and n1 (s)the number of l’s in s. Which one of the following languages is not regular? (Solved)
1. L = {s € (0 + 1)*n0 (s) is a 3-digit prime
2. L = {s € (0 + 1)* | for every prefix s’ of s, l 0 (s’) — n1 (s’) | <= 2 }
3. L={s € (0+1)* | n0(s) - n1(s) | <= 4}
4. L = {s € (0 + 1) | n0 (s) mod 7 = n1 (s) mod 5 = 0 }
- c. L={s € (0+1)* | n0(s) - n1(s) | <= 4}