Как L = {a ^ nb ^ m | n, m> = 1, n! = 3m} не является регулярным?

Question

Я борюсь с пониманием этой проблемы. У кого-нибудь есть идеи?

Редактировать: Это было ... n, m <1 ..., однако мой вопрос ... n, m> = 1 ...

Answer 1

Если n и m меньше или равны 1, то этот язык фактически является регулярным, поскольку он является конечным языком {a, b, ab}. Если вместо этого вы имели в виду, что n и m больше или равны 1, то анализ становится более сложным.

Если предположить, что n и m больше или равны 1, язык бесконечен и может или не может быть регулярным Я чувствую, что этот язык будет трудно или невозможно доказать нерегулярно, используя лемму прокачки для обычных языков. Здесь есть два более простых метода доказательства: теорема Майхилла-Нерода и свойства замыкания регулярных языков.

Чтобы доказать, что язык нерегулярен с помощью Myhill-Nerode, нам нужно идентифицировать бесконечную последовательность строк которые все различимы по отношению к нашему языку. Две строки различимы по отношению к нашему языку, если они имеют разные наборы строк, которые могут быть объединены на них, чтобы получить строку в нашем языке. Рассмотрим строки aaa, aaaaaa,…, a ^ 3k,…. Самые короткие строки, которые не могут быть соединены с ними для получения строк на нашем языке, это b, bb,…, b ^ k,…. Это означает, что каждая строка a ^ 3k различима по отношению к нашему языку; наборы строк, которые могут быть объединены с нашими строками, зависят от параметра k. Это показывает, что существует бесконечно много классов эквивалентности в отношении неразличимости относительно нашего языка. Это означает, что минимальный DFA для нашего языка будет иметь бесконечно много состояний, противоречие.

Чтобы доказать, что язык нерегулярен с использованием свойств замыкания, рассмотрим следующие языки:

L = {a^n b^m | n, m >= 1, n != 3m}
R = {a^n b^m | n, m >= 1, n = 3m}
S = {a^n b^m | n, m >= 1}

Во-первых, обратите внимание, что R нерегулярно (доказательство этого просто с помощью леммы о накачке) и что S регулярно (это регулярный язык aa bb ).

Далее отметим, что S \ L = R (здесь \ обозначает разность множеств).

Однако это противоречие, так как мы предполагали, что L регулярный, мы знаем, что S регулярный, и мы знаем, что регулярные языки закрыты при разности множеств (мы может создать DFA для различий двух обычных языков, используя конструкцию Cartesian Product Machine). Разница между двумя регулярными языками не может быть нерегулярным языком R, поэтому мы доказали от противного, что L должен быть нерегулярным.

Answer 2

Вот другой способ показать нерегулярность, используя свойства замыкания.

Интуитивно, мы ожидаем, что язык {a ³ⁿ b ⁿ | n ∈ N} быть нерегулярным, поскольку по сути это канонический язык «n копий a, затем n копий b», немного растянутый. Если вас устраивает мысль о том, что этот язык не является регулярным, отлично! Если нет, вы можете написать краткое доказательство этого, используя либо теорему Майхилла-Нерода, либо лемму прокачки.

Имея это в виду, язык L = {a ⁿ b ^м | n ≠ 3n} очень тесно связано с приведенным выше. По сути, это своего рода «противоположность» вышеперечисленного языка. Итак, давайте сформируем дополнение L 'всех строк, которые не появляются в L. Это будут все строки вида a ³ⁿ b ⁿ , а также все строки, которые не были соответствует b . И эй! Если L регулярно, то и L '.

Поскольку в L' есть некоторые строки, которые нам не нужны, давайте пересечем его с b , чтобы просто получить строки, которые мы хотеть. Пересечение обычного языка с обычным языком возвращает обычный язык, что означает, что L '∩ a b является регулярным, если L' есть. Но это тот язык, который мы видели выше, который, как мы знаем, не является регулярным! Это означает, что L тоже нет, и мы закончили!