If s is a string over (0 + 1)* then let n0(s) denote the number of 0’s in s…
2006
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 1’s in s. Which one of the following languages is not regular?
- A.
A
- B.
B
- C.
C
- D.
D
Attempted by 29 students.
Show answer & explanation
Correct answer: C
A)There is a finite number of 3-digit primes. Since the set of such strings is finite, and all finite languages are regular, this language is regular.
B) This language is regular because the difference is bounded at every step. If the difference ever exceeds 2, the string is rejected immediately. This can be represented by a DFA with a small, finite number of states.
c)Infinite Counting Required: In option C, the condition must hold for the entire string .
Unlike option B, which checks every prefix, this language allows the difference to fluctuate significantly (e.g., a million 0's followed by a million 1's) as long as the final difference is
<=4.
D)This language is regular because it uses modulo arithmetic. An automaton only needs to keep track of the remainder (0-6 for 0's and 0-4 for 1's), which requires a finite number of states (specifically, states).