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

Concept

Two facts govern this problem. First, the Myhill–Nerode theorem: a language is regular exactly when it induces only finitely many equivalence classes on strings, where two strings are equivalent if every suffix behaves identically with respect to membership; an infinite family of pairwise-distinguishable prefixes rules out regularity. Second, a closure fact: the Kleene star of any subset of a single-symbol language depends only on which non-negative integers (lengths) are reachable by repeatedly adding the lengths already present, and every additive submonoid of the natural numbers is finitely generated — hence eventually periodic — and an eventually periodic unary length-set is always regular.

Applying the Myhill–Nerode argument to L1:

1. Take the infinite family of prefixes 0^p indexed by each prime p.

2. For two distinct primes p and q, append q ones to each: gcd(p,q) = 1 (distinct primes share no common factor), so 0^p1^q is in L1; but gcd(q,q) = q ≠ 1, so 0^q1^q is not in L1. The suffix 1^q distinguishes 0^p from 0^q.

3. Since this holds for every pair of distinct primes, and there are infinitely many primes, the prefixes {0^p : p prime} are pairwise distinguishable.

4. Hence the Myhill–Nerode relation has infinitely many equivalence classes.

5. Therefore L1 is not regular.

Applying the submonoid argument to L2*:

1. Let L2 ⊆ 0* and let S = {k : 0^k ∈ L2} be the set of lengths present in L2.

2. Every string in L2* is a concatenation of blocks from L2, so its length is a sum of elements of S; the length-set of L2* is exactly the additive submonoid ⟨S⟩ generated by S.

3. Every submonoid of (N,+) is finitely generated — if it had infinitely many minimal generators, two of them would collide modulo the smallest one, a contradiction — so ⟨S⟩ = ⟨n1,…,nk⟩ for finitely many n1,…,nk ∈ S. (In the degenerate case S = ∅, i.e. L2 contains no string at all, ⟨S⟩ = {0} and L2* = {ε}, which is trivially regular.)

4. A submonoid generated by finitely many naturals is eventually periodic: past a bound, the reachable lengths recur with period gcd(n1,…,nk), apart from finitely many exceptions.

5. A unary language whose length-set is eventually periodic is recognised by a DFA that tracks the count modulo that period plus a finite prefix table, so L2* is regular for every subset L2 of 0*.

Cross-check with concrete numbers:

• For L1: take the primes p = 2 and q = 5. Then 0^2 1^5 has gcd(2,5) = 1, so it is in L1, while 0^5 1^5 has gcd(5,5) = 5, so it is not — confirming the prime-indexed distinguishability argument.

• For L2*: take L2 = {0^6, 0^10}. The reachable lengths (sums of 6's and 10's) are 6, 10, 12, 16, 18, 20, 22, 24, … — eventually every even number from 12 onward, a periodic pattern with period gcd(6,10) = 2, exactly as the general argument predicts.

Result

Therefore L1 is not regular, while L2* is regular for every subset L2 of 0* — matching the option that pairs ‘L1 not regular’ with ‘L2* regular’.