Клини замыкание для бесконечного подмножества

Question

Пусть L = {aⁿ | n> = 0}, где а также для всех n >= 1.

Таким образом, L состоит из последовательностей любой длины, включая последовательность длины 0. Пусть L2 - любое бесконечное подмножество L. Мне нужно показать, что всегда существует DFA для распознавания (L2)*.

Если L2 - конечное подмножество, это очень очевидно, так как L2 будет DFA и, следовательно, по клине замыкания L2* будет распознан DFA. Но я не могу получить его для бесконечного подмножества, так как L2 не может быть выражен как DFA, например, длина строк проста.

Answer 1

Подход

Хотя существует DFA для описания множества L всех строк a ⁿ, n> = 0, нет гарантии, что DFA существует для всех подмножеств L. Подмножество L, которое содержит все строки, длина которых проста, как вы упомянул, является одним из примеров, где DFA описывает язык не существует.

Правильный подход заключается в прямом доказательстве того, что (L')* является регулярным языком для любого подмножества L' в L.

Определение

Определим GCD(K) = GCD _{w ∈ K, | w | > 0} (| w |), где K - любое непустое подмножество в L. Теперь мы можем ссылаться на наибольший общий делитель всех длин всех непустых слов в языке K как GCD(K). Это определение применимо как к конечному, так и к бесконечному подмножеству L.

Аналогично можно определить LCM (K) = LCM _{w ∈ K, | w | > 0} (| w |), где K - любое непустое и конечное подмножество в L.

доказательство

Мы попытаемся доказать, что когда GCD(L') = 1, существует такое число M, что вся строка a ⁿ, n> = M принадлежит языку (L')*. Это приводит к тому, что (L')* является регулярным языком, поскольку мы можем построить регулярное выражение в форме:

Все строки длиной меньше М и принадлежат (L')*
ИЛИ ЖЕ
Все строки длиной больше или равны M

Приведенное выше регулярное выражение имеет соответствующий DFA с M + 1 состояниями.

Когда GCD(L') > 1, мы можем свести проблему к случаю GCD = 1, "разделив" все слова в подмножестве L' на GCD(L').

---

Если GCD(L') = 1 (взаимно простое множество), существует конечное подмножество S в L', где GCD длины всех строк в S также равен 1.

Мы можем доказать вышеизложенное утверждение конструкцией.

• Выберите любой элемент w ₁ из L ', | w ₁ | > 0 и построить множество S ₁ = {w ₁ }
• Если GCD(S _n) = 1, S _n - это множество, которое мы хотим найти.
• Если GCD(S _n)> 1, выбрать элемент w _{n + 1} из L 'и построить множество S _{n + 1} = {w _{n + 1} } ∪ S _n, так что
  GCD(S _{n + 1}) n)

Если GCD(S _n)> 1, всегда существует элемент из множества L ', который уменьшает GCD, когда мы добавляем его в набор; в противном случае GCD множества L 'не может быть 1. А поскольку длина первого элемента w ₁ имеет конечное число факторов, размер конечного множества S конечен.

Возвращаясь к задаче, для любого подмножества L 'в L мы можем найти конечное подмножество S в L', которое удовлетворяет GCD(L ') = GCD(S). Из множества S мы можем построить обобщенное линейное диофантово уравнение с |S| неизвестные а _я:

a ₁ | w ₁ | + a ₂ | w ₂ | +... + a _|S| | w _|S| | = c, где c - неотрицательное целое число

Поскольку GCD(S) = 1, приведенное выше уравнение всегда разрешимо, рекурсивно применяя решение к простейшей форме линейного диофантова уравнения ax + by = c.

Решите приведенные выше обобщенные диофантовы уравнения для c = 0 до (LCM(S) - 1). Решения (a ₁, a ₂,..., a _|S|) могут содержать отрицательные числа. Однако мы можем продолжать добавлять кратные значения LCM (S) к обеим сторонам уравнений, пока все решения не содержат только неотрицательные числа.

Пусть k будет наименьшим кратным LCM (S), так что все диофантовы уравнения для c = k * LCM(S) + q, q = 0 до (LCM (S) - 1) имеют неотрицательное решение. Тогда мы можем определить M как k * LCM(S), поскольку любые строки, длина которых больше, чем M, могут быть разложены как объединение слов в S (таким образом, в L ').

Пример расчета на основе доказательства

Предположим, что L '- множество всех строк в L, длина которых проста.

Построим множество S = {a ², a ⁵ }. S может быть {a ², a ¹⁹ } или {a ⁵, a ²³ }, на самом деле не имеет значения. Конечное значение M может быть другим, но это не влияет на тот факт, что (L')* является обычным языком.

Нам нужно решить 10 уравнений (отдельно):

2a ₁ + 5a ₂ = 0 => (a ₁, a ₂) = (0, 0)
2a ₁ + 5a ₂ = 1 => (a ₁, a ₂) = (3, -1)
2a ₁ + 5a ₂ = 2 => (a ₁, a ₂) = (1, 0)
2a ₁ + 5a ₂ = 3 => (a ₁, a ₂) = (-1, 1)
2a ₁ + 5a ₂ = 4 => (a ₁, a ₂) = (2, 0)
2a ₁ + 5a ₂ = 5 => (a ₁, a ₂) = (0, 1)
2a ₁ + 5a ₂ = 6 => (a ₁, a ₂) = (3, 0)
2a ₁ + 5a ₂ = 7 => (a ₁, a ₂) = (1, 1)
2a ₁ + 5a ₂ = 8 => (a ₁, a ₂) = (4, 0)
2a ₁ + 5a ₂ = 9 => (a ₁, a ₂) = (2, 1)

Добавьте один LCM(2,5) = 10. Обратите внимание, что мы можем изменить решение напрямую, без повторного решения, благодаря свойству LCM:

2a ₁ + (5a ₂ + 10) = 1 + 10 => (a ₁, a ₂) = (3, 1)
(2a ₁ + 10) + 5a ₂ = 3 + 10 => (a ₁, a ₂) = (4, 1)

Поскольку все решения неотрицательны, и мы добавляем только один LCM(2,5), M = 10.

Регулярное выражение для (L')* может быть построено:

a ² + a ⁴ + a ⁵ + a ⁶ + a ⁷ + a ⁸ + a ⁹ + a ¹⁰ a *

Регулярное выражение не очень компактно, но это не наша задача. Для доказательства нам нужно только знать, что существует число M, так что a ⁿ принадлежит (L')* для всех n >= M, из чего следует, что существует конечное число состояний и можно построить DFA.,