Consider the following two languages: \(L_1=\{0^i1^j \mid ged (i,j)=1 \}\)…

Answer: The language of pairs with gcd(i,j)=1 is not regular, and the Kleene star of any subset of 0* is regular.

Why the gcd language is not regular:

• Consider all strings of the form 0^n (no ones). For two different numbers n ≠ m, pick a prime p that divides one of n or m but not the other (such a prime exists because their prime factorizations differ).

• Append 1^p to both: gcd(n,p)=1 but gcd(m,p)≠1 (or vice versa). Thus 0^n1^p is in the language while 0^m1^p is not, so 0^n and 0^m are distinguishable.

• Since there are infinitely many distinct n giving pairwise distinguishable prefixes, the Myhill–Nerode relation has infinitely many equivalence classes, so the language is not regular.

Why the Kleene star of any subset of 0* is regular:

• Let L2 be any subset of 0*. View each string 0^k by its length k. The set of lengths of strings in L2* is the submonoid of (N,+) generated by the lengths of strings in L2.

• Every additive submonoid of the natural numbers is finitely generated, so the set of lengths in L2* is generated by finitely many integers and therefore is ultimately periodic.

• A unary language whose set of lengths is ultimately periodic is regular. Hence L2* is regular for any L2 ⊆ 0*.

Therefore the correct statement is: L1 is not regular, and L2* is regular.