Предположим, что L содержит две строки 0 ^ n и 0 ^ m и что n и m не имеют общих множителей: они относительно простые. Затем путем объединения некоторого числа экземпляров 0 ^ n с некоторым количеством экземпляров 0 ^ m можно сформировать любую строку длины (n - 1) (m - 1). Поскольку L *, следовательно, должно исключать только конечное число слов, дополнение (L *) 'должно быть конечным, следовательно, регулярным; поскольку обычные языки закрыты в дополнении, L * тоже должен быть регулярным.
Откуда (n - 1) (m - 1) пришел? Что ж, это особый случай (n = 2) задачи для монет , для которого у нас есть решение в замкнутой форме. Вы должны быть в состоянии исследовать это и найти некоторые доказательства.
Как насчет случая, когда все строки в L имеют длины, кратные некоторому GCD, скажем, g? Ну, доказательство регулярности очень похоже; рассмотрим модифицированный алфавит, где 0 заменяется символом (0 ^ g), а затем докажем, что аналогичный язык для этого алфавита является регулярным, как указано выше. Другими словами, вы можете показать, что L * содержит только строки, кратные g, и все строки, кратные g длины не менее (n / g - 1) (m / g - 1), где n и m имеют GCD g. Язык является регулярным, потому что он исключает только конечное число слов, длина которых делится на g.