wL∗LL˚wL˚L∗=L˚∗L˚L∗
Пусть подмножество и слова в . можно выразить как конкатенацию слов в еслиможет быть выражено в виде суммы элементов , где представляет собой набор длин слов в . Таким образом, проблема сводится к выражению целого числа в виде суммы целых чисел в определенном наборе (с разрешенными повторениями): canбыть выражено как с и ?MLwLwL|w|S⊂NSM|w|k1s1+…+kmsm∀i,si∈Sk1∈N
Это хорошо известная проблема арифметики, и ответ если коэффициенты могут быть отрицательными ( ),представима тогда и только тогда оно кратно наибольший общий делитель элементов : . С требованием неотрицательных коэффициентов это все еще справедливо для достаточно больших,(ki)ki∈Z|w|SgcdS|w|
Рассмотрим бесконечную последовательность определенную как . Это убывающая последовательность целых чисел (начиная с , поэтому она постоянна после определенного индекса ; и По китайской теореме об остатках любой элемент из может быть выражается как с и . Если и тогда вы можете выбрать все неотрицательные коэффициенты.(gi)i≥minSgi=gcd(S∩[0,i])gminS=minSjgj=gcdSSk1s1+…+kmsm∀i,ki∈Z{s1,…,sm}=S∪[0,j]x∈Sx≥s1⋅…⋅sm
Достаточно арифметики. Пусть . Каждое слово в может быть выражено как объединение слов в , длина которых не , то есть . Так как у нас также есть , у нас есть , который является регулярным, поскольку конечен, следовательно, регулярен.L˚={w∈L∣|w|≤gj}LLgjL⊆L˚∗L˚⊆LL∗=L˚∗L˚
В качестве альтернативы используйте характеристику обычных языков в однобуквенных алфавитах .