For S ∈ (0 + 1) * let d(s) denote the decimal value of s (e.g. d(101) = 5).…
2006
For S ∈ (0 + 1) * let d(s) denote the decimal value of s (e.g. d(101) = 5). Let L = {s ∈ (0 + 1)* d(s)mod5 = 2 and d(s)mod7 != 4}. Which one of the following statements is true?
- A.
L is recursively enumerable, but not recursive
- B.
L is recursive, but not context-free
- C.
L is context-free, but not regular
- D.
L is regular
Attempted by 25 students.
Show answer & explanation
Correct answer: D
The language L consists of binary strings where the decimal value satisfies two conditions: d(s) mod 5 = 2 and d(s) mod 7 ≠ 4. Both conditions are periodic and can be checked using finite automata since modular arithmetic over fixed moduli (5 and 7) results in regular properties. The intersection of two regular conditions remains regular, so L is regular. Therefore, the statement that L is regular (option D) is correct.
A video solution is available for this question — log in and enroll to watch it.