While reading from a book I had this doubt.
It mentions that
L = {s ∈ (0+1)* | n0(s) mod 7 = n1(s) mod5 =0} is regular Where n0(s) = number of 0’s in s and n1(s) = number of 1’s in s
Further it mentions that
L = {s ∈ (0 + 1)* | d(s) mod 5 =2 and d(s) mod 7 !=4 } is not regular (not even context-free but it is recursive) Where d(s) = decmial value of s (e.g. d(101) = 5)
Why is it so? Is it because a DFA doesn’t have memory to store (remember) the decimal value of s? But in that case how come the first language is given to be regular?
There is either a mistake in your textbook or you are misreading it: the second language you name is regular.
A DFA can compute the value of a binary number (or any base number) modulo m (for any m). Simply have m states numbered 0 to m-1; when reading a zero, go from the current state s to (s*2) mod m; when reading a one, go to (s*2+1) mod m. To see that this works, one needs only to look at how binary works, and that (a + b) mod m = (a mod m + b mod m) mod m (and similarly for multiplication).
To accept numbers which are equal to k mod m, make k an accepting state; to accept numbers different from k mod m, make all other states accepting. This means {s ∈ {0,1}* | d(s) mod 5 = 2} and {s ∈ {0,1}* | d(s) mod 7 != 4 } are both regular languages. The language L is their intersection, and the regular languages are closed under intersection, so L is regular.
The language {s ∈ {0,1}* | d(s) mod 5 = 2} is accepted by the regular expression '(((0*10(10*10)*10*11|0*11)((00|1)(10*10)*10*11|01)*(00|1)(10*10)*0|0*10(10*10)*0)(0((00|1)(10*10)*10*11|01)*(00|1)(10*10)*0|1)*0((00|1)(10*10)*10*11|01)*(00|1)(10*10)*|(0*10(10*10)*10*11|0*11)((00|1)(10*10)*10*11|01)*(00|1)(10*10)*|0*10(10*10)*)$' (I have used Python notation here, but to obtain your notation simply replace | by + and remove the $).