Identification of Regular

Question

Identify weather the following language is regular?

∀m,n ∈ N

1)a^m b^n | LCM(m,n)=0

2)a^m b^n | LCM(m,n)=1

3)a^m b^n | LCM(m,n)<100

4)a^m b^n | GCD(m,n)=1

Answer 1

2: LCM(M.N) =1 iff m=1,n=1   --> Regular

3: LCM(M,N)<100 for finite number of m & n  , number of strings becomes finite -->Regular

4:GCD(M,N)=1 , their could be infinite  combination of m & n which are relatively prime to each other -->Non Regular

Comments

LCM(M.N) =0 when m=0 or n= 0 or both m=n=0. So the language is {a⁺ ∪ b⁺  ∪ Epsilon}. This is union of regular language which is also regular.

a⁺ is when n=0 i.e. 0 occurrences of b.

b⁺ is when m=0 i.e. 0 occurrences of a.

Epsilon when 0 occurrences of both.

Is it correct?

---

In LCM we do not count 0 as a common multiple, if we count 0 as a common multiple the 0 would be the LCM of any m & n as m*0=0 and n*0=0  

In context of TOC we could make an exception where definition of LCM would deviate from its mathematical definition  when m=0 or n= 0 or both m=n=0 .............which would give the answer as REGULAR LANGUAGE