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

CONCEPT

The Myhill–Nerode theorem says that a language is regular exactly when it has finitely many equivalence classes under indistinguishability by suffixes. An infinite family of prefixes separated by suitable suffixes therefore proves non-regularity.

For a unary language, concatenation adds string lengths. Thus the length set of a Kleene star is an additive submonoid of the non-negative integers; every such submonoid is finitely generated, and every nonzero one is eventually periodic. An eventually periodic unary length set is regular.

APPLICATION: THE GCD LANGUAGE

1. Take the infinite family of prefixes 0^p, one for each prime p.

2. For distinct primes p and q, append the common suffix 1^q. Then gcd(p,q)=1, so 0^p1^q belongs to L_1, whereas gcd(q,q)=q≠1, so 0^q1^q does not.

3. The suffix 1^q distinguishes 0^p from 0^q. Infinitely many prime-indexed prefixes are therefore pairwise distinguishable, so L_1 is not regular.

APPLICATION: THE UNARY STAR

1. Let S={k:0^k∈L_2}. The strings in L_2^* have exactly the lengths in the additive submonoid M=⟨S⟩.

2. If S is empty or contains no positive length, then M={0} and L_2^*={ε}, which is regular.

3. Otherwise, M is a nonzero submonoid of the non-negative integers. It has a finite generating set; if d is the gcd of its positive generators, all sufficiently large multiples of d lie in M and no nonmultiple does. Hence membership is eventually periodic with period d.

4. A DFA handles the finite initial segment explicitly and then tracks the input length modulo d. Therefore L_2^* is regular for every subset L_2 of 0^*.

CROSS-CHECK

• For p=2 and q=5, the suffix 1^5 gives gcd values 1 and 5 for the prefixes 0^2 and 0^5, demonstrating the distinguishing-suffix mechanism.

• For L_2={0^6,0^10}, the reachable positive lengths include 6, 10, 12, 16, 18, 20, 22, …; 14 is absent, but every even length from 16 onward is reachable, giving eventual period 2.

• For L_2={ε}, the star is still {ε}, confirming the zero-length branch.

RESULT

Thus L_1 is not regular and L_2^* is regular, so the saved pair is the correct one.