Whether an alphabet and let u = a1...ak ∈ Σ*. We define uR = ak ak-1...a2 a1.
Use the theorem of Myhill-Nerode to prove that
1. L = { w ∈ Σ*:∃u ∈ Σ*;w = uuR }. is not regular for Σ= {a, b, c}.
2. L = c w ∈ Σ*:∃u ∈ Σ*; w =uuR } is regular for Σ={a}.
3. L = { w ∈ {0,1}* :w ≡0 (mod m) } is regular whatever m ∈ N
(w read as a natural binary)