GATE 2006 - 30

Question

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

Answer 1

We can have a finite automata for    d(S) mod 5   and d(S)mod 7 != 4

Now, intersection of regular language is regular.

 

Hence, option D

Comments

L₁ = {s ∈ (0 + 1)* d(s)mod5 = 2 }

L₂ = {s ∈ (0 + 1)*  d(s)mod7 != 4}

so L₁ ={10,111,1100,10001,....}

and L₂ = {0,1,10,11,101,110,111,1000,1001,1010,1100,....}

L= L1  ∩  L2

But I have no idea how to create a dfa for any one of these language. So, please guide me to create a dfa for accepting any one laguage L₁ or L₂ 

Answer 2

Let L1 = {s ∈ (0 + 1)* | d(s) mod5 = 2}, we can construct the DFA for this which will have 5 states (remainders 0,1,2,3,4)
L2 = {s ∈ (0 + 1)* | d(s) mod7 = 4}, we can construct the DFA for this which will have 7 states (remainders 0,1,2,3,4,5,6)
Since L1 and L2 have DFAs, hence they are regular. So the resulting Language.
L = L1 ∩ L2 (compliment) must be regular (by closure properties, INTERSECTION of two regular languages is a regular language).