This problem concerns languages over the alphabet Σ = {1}. For any two integers q, r ≥0, define the language Lr, q over Σ as
Lr, q ={1mq+r : m ≥0}={1q,1q+r,12q+r,...}.
For instance, L1,3 ={1,1111,1111111,...}.
(a) Show that for every q and r, the language Lr, q is regular.
(b) Show that if L is a regular language over Σ, then L can be written as
L = Lr1,q ∪ Lr2,q ∪···∪ Lrk, q ∪ L0,
where 0 ≤ r1 < ··· < rk are integers and L0 is a finite set.