Question

For S ∈ (0+1)* let d(S) denotes the decimal value of S (e.g., d(101) = 5).
Let L = S ∈ (0+1)* | d(s) mod 5 = 2 and d(s) mod 7 ≠ 4
Which one of the following statements is true?

• A. L is recusively enumerable, but not recursive
• B. L is recursive, but not context-free
• C. L is context-free, but not regular
• D. L is regular

Answer 1

The correct option is D L is regular

There is a DFA corresponding to d(S) mod 5 = 2 as well as d(S) mod 7 ≠ 4. Therefore, both of them are regular languages. Let, they be L₁ and L₂. The given language is L₁ ∩ L₂
Since regular languages are closed under intersection and complementation, the given language is also regular.