wL∗LL˚wL˚L∗=L˚∗L˚L∗
Deje que sea un subconjunto de y una palabra en . puede expresarse como una concatenación de palabras en iffpuede ser expresada como una suma de elementos de , donde es el conjunto de longitudes de palabras en . Por lo tanto, el problema se reduce a expresar un número entero como una suma de números enteros en un conjunto particular (con repeticiones permitidas): canse expresará como con y ?MLwLwL|w|S⊂NSM|w|k1s1+…+kmsm∀i,si∈Sk1∈N
Este es un problema bien conocido en aritmética, y la respuesta es que si los coeficientes pueden ser negativos ( ),es expresable si y sólo si es un múltiplo del máximo común divisor de los elementos de : . Con un requerimiento de coeficientes no negativos, esto todavía es válido para.(ki)ki∈Z|w|SgcdS|w|
Considere la secuencia infinita definida por . Esta es una secuencia decreciente de enteros (comenzando con , por lo que es constante después de cierto índice ; y Según el teorema del resto chino, cada elemento de puede ser expresado como con y . Si y entonces puede elegir todos los coeficientes no negativos.(gi)i≥minSgi=gcd(S∩[0,i])gminS=minSjgj=gcdSSk1s1+…+kmsm∀i,ki∈Z{s1,…,sm}=S∪[0,j]x∈Sx≥s1⋅…⋅sm
Suficiente aritmética. Deje . Cada palabra en puede expresarse como una concatenación de palabras en cuya longitud es como máximo , es decir, . Como también tenemos , tenemos , que es regular ya que es finito, por lo tanto, regular.L˚={w∈L∣|w|≤gj}LLgjL⊆L˚∗L˚⊆LL∗=L˚∗L˚
Alternativamente, use la caracterización de idiomas regulares en alfabetos de una letra .