Как доказать, что язык не является регулярным?

cs.stackexchange https://cs.stackexchange.com/questions/1031

Вопрос

Мы узнали о классе обычных языков $ mathrm {reg} $. Он характеризуется какой-либо одной концепцией среди регулярных выражений, конечных автоматов и левой линейной грамматики, поэтому легко показать, что данный язык является регулярным.

Как мне показать наоборот, хотя? Мой TA был непреклонен, что для этого мы должны были бы показать для всех регулярных выражений (или для всех конечных автоматов или для всех левых линейных грамматиков), что они не могут описать язык под рукой. Это кажется большой задачей!

Я читал о какую -то накачанную лемму, но это выглядит очень сложно.

Это предназначено для того, чтобы быть справочным вопросом, собирающим обычные методы доказательства и примеры применения. Видеть здесь Для того же вопроса на языках без контекста.

Это было полезно?

Решение

Доказательство по противоречию часто используется, чтобы показать, что язык не является регулярным: пусть $ p $ собственность верно для всех обычных языков, если ваш конкретный язык не проверяет $ p $, то это не регулярно. Можно использовать следующие свойства:

  1. Насосная лемма, как показано в Ответ Дэйва;
  2. Свойства закрытия обычных языков (установленные операции, конкатенация, звезда Kleene, зеркало, гомоморфизмы);
  3. Регулярный язык имеет конечное количество класса эквивалентности префикса, Myhill -Dnerode Теорема.

Чтобы доказать, что язык $ l $ не регулярно использует свойства закрытия, метод состоит в том, чтобы объединить $ l $ с обычными языками по операциям, которые сохраняют регулярность, чтобы получить язык, который, как известно, не регулярно, например, архетипический язык $ i = {a^nb^n | n in mathbb {n} } $. Например, пусть $ l = {a^pb^q | P neq q } $. Предположим, что $ l $ является регулярным, так как регулярные языки закрываются в комплементации, поэтому $ l $ дополнение $ l^c $. Теперь возьмите пересечение $ l^c $ и $ a^ star b^ star $, что является регулярным, мы получаем $ i $, что не является регулярным.

Теорема Myhill -Dnerode может быть использована, чтобы доказать, что $ i $ не регулярно. Для $ p geq 0 $, $ i/a^p = {a^{r} b^rb^p | r in mathbb {n} } = i. {b^p } $. Все классы разные, и существует необратимая бесконечность таких классов. Как обычный язык должен иметь конечное количество классов $ i $ не регулярно.

Другие советы

Основываясь на ответе Дэйва, вот пошаговое «руководство» для использования накачанной леммы.

Вспомните накачанную лемму (взятая из ответа Дэйва, взята в Википедию):

Позволять $ L $ быть обычным языком. Тогда существует целое число $ n ge 1 $ (в зависимости только от $ L $) так, чтобы каждая строка $ w $ в $ L $ по крайней мере $ n $ ($ n $ называется «длина накачки») может быть написана как $ w = xyz $ (т.е., $ w $ можно разделить на три подстроения), удовлетворяя следующие условия:

  1. $ | y | ge 1 $
  2. $ | XY | le n $ а также
  3. «накачанный» $ w $ все еще в $ L $: для всех $ i ge 0 $, $ xy^iz in l $.

Предположим, что вам дают какой -то язык $ L $ И вы хотите показать, что это не регулярно с помощью насосной леммы. Доказательство выглядит так:

  1. Предположить, что $ L $ является обычный.
  2. Если это регулярно, то насосная лемма говорит, что существует некоторое число $ n $ которая является длиной накачки.
  3. Выберите специфический слово $ w in l $ длины больше, чем $ n $. Анкет Сложная часть - знать, какое слово нужно взять.
  4. Рассмотреть возможность ВСЕ Способы разбиения $ w $ в 3 части, $ w = xyz $, с $ | xy | le n $ а также $ y $ не пустой. За каждый Из этих способов, покажите, что его нельзя накачать: всегда существует некоторые $ i ge 0 $ так что $ xy^iz notin l $.
  5. Сделать вывод: слово $ w $ не может быть «накачан» (независимо от того, как мы его разделяем $ xyz $) В противоречии накачанной лемме, то есть наше предположение (Шаг 1) неправильно: $ L $ не регулярно.

Прежде чем мы перейдем к примеру, позвольте мне повторить шаг 3 и шаг 4 (здесь большинство людей идут не так). На шаге 3 вам нужно выбрать одно конкретное слово в $ L $. Анкет Запишите это явно, как "00001111" или "$ a^nb^n $". Примеры для вещей, которые нет конкретное слово: "$ w $«Или« слово, которое имеет 000 в качестве префикса ».

С другой стороны, на шаге 4 вы должны рассмотреть более одного случая. Например, если $ w = 000111 $ Недостаточно сказать $ x = 00, y = 01, z = 00 $, а затем достигните противоречия. Вы также должны проверить $ x = 0, y = 0, z = 0111 $, а также $ x = epsilon, y = 000, z = 111 $, и все остальные возможные варианты.

Теперь давайте следуем по шагам и докажем, что $ L = {0^k1^{2k} mid k> 0 } $ не регулярно.

  1. Предполагать $ L $ это регулярно.
  2. Позволять $ n $ Будьте длиной накачки, данной насосной леммой.
  3. Позволять $ w = 0^n 1^{2n} $.
    (санитарная проверка: $ | w | gt n $ по мере необходимости. Почему это слово? Другие слова также могут работать ... требуется какой -то опыт, чтобы придумать правильное $ w $) Опять же, обратите внимание, что $ w $ это конкретное слово: $ Underbrace {000 ldots0} _ {n text {times}} anderbrace {111 ldots1} _ {2n text {times}} $.
  4. Теперь давайте начнем рассмотреть различные случаи, чтобы разделить $ w $ в $ xyz $ с $ | xy | le n $ а также $ | y |> 0 $. Анкет С $ | XY | Независимо от того, как мы разделились $ w $, $ x $ будет состоять только из 0, как и $ y $. Анкет Предположим $ | x | = s $ а также $ | y | = k $. Анкет Нам нужно рассмотреть все варианты, это все возможное $ s, k $ так что $ s ge 0, k ge 1 $ а также $ s+k le n $. ДЛЯ ЭТОГО $ L $ Доказательство для всех этих случаев одно и то же, но в целом это может быть иначе.
    брать $ i = 0 $ и рассмотрим $ xy^iz = xz $. Анкет Это слово не в $ L $ Поскольку это форма $ 0^{nk} 1^{2n} $ (не важно что $ S $ а также $ k $ были), и с тех пор $ k ge 1 $, это слово не в $ L $ И мы достигаем противоречия.
  5. Таким образом, наше предположение неверно, и $ L $ не регулярно.

Клип на YouTube, который объясняет, как использовать насосную лемму в тех же линии, которую можно найти здесь

Из Википедии, Язык накачки для обычных языков это следующее:

Пусть $ l $ будет обычным языком. Тогда существует целое число $ P Ge 1 $ (в зависимости только от $ l $), так что каждая строка $ w $ v $ l $ длиной не менее $ p $ ($ p $ называется «длиной накачки») может Будьте написаны как $ w = xyz $ (то есть $ w $ можно разделить на три подстроения), удовлетворяя следующие условия:

  1. $ | y | ge 1 $
  2. $ | XY | le p $ и
  3. Для всех $ i ge 0 $, $ xy^iz in l $.
    $ y $ - это подстроение, которое можно накачать (удаляется или повторяет любое количество раз, и полученная строка всегда находится в $ l $).

(1) означает, что петля, которая должна быть перекачена, должна быть длиной не менее одного; (2) означает, что цикл должен происходить в рамках первых символов P. Там нет ограничений на x и z.

Проще говоря, для любого обычного языка L любое достаточно длинное слово $ w in l $ можно разделить на 3 части. т.е. $ w = xyz $, так что все строки $ xy^kz $ для $ k ge 0 $ также находятся в $ l $.

Теперь давайте рассмотрим пример. Анкет Пусть $ l = {(01)^n2^n mid n ge0 } $.

Чтобы показать, что это не регулярно, вам нужно рассмотреть, как выглядят все разложения $ w = xyz $ $ (мы решили посмотреть на это конкретное слово длиной $ 3P $, где $ P $ - это длина накачки). Нам нужно рассмотреть, где происходит часть строки $ y $. Он может совпадать с первой частью и, таким образом, будет равным либо $ (01)^{k+1} $, $ (10)^{k+1} $, $ 1 (01)^k $ или $ 0 (10)^ k $, за $ k ge 0 $ (не забудьте, что $ | y | ge 1 $). Это может совпадать со второй частью, что означает, что $ y = 2^k $, за $ k> 0 $. Или он может перекрываться по двум частям слова, и будет иметь форму $ (01)^{k+1} 2^l $, $ (10)^{k+1} 2^l $, $ 1 (01 )^k 2^l $ или $ 0 (10)^k 2^l $, для $ k ge0 $ и $ l ge1 $.

Теперь накачивайте каждый, чтобы получить противоречие, которое будет словом, не на вашем языке. Например, если мы возьмем $ y = 0 (10)^k2^l $, накачанная лемма говорит, например, что $ xy^2z = x0 (10)^k2^l0 (10)^k2^lz $ Будьте на языке, для соответствующего выбора $ x $ и $ z $. Но это слово не может быть на языке, так как $ 2 $ появляется до 1 $.

Другие случаи приведут к тому, что число $ (01) $ будет больше, чем число $ 2 $ 'или наоборот, или приведет к словам, которые не имеют структуры $ (01)^n2^n $ Например, имея два $ 0 $ подряд.

Не забывайте, что $ | XY | le p $. Здесь полезно сократить доказательство: многие из приведенных выше декомпозиций невозможно, потому что они станут частью $ Z $ слишком долго.

Каждый из приведенных выше случаев должен привести к такому противоречию, что тогда было бы противоречием накачанной леммы. Вуаля! Язык не будет регулярным.

Для данного языка $ l subteq sigma^*$, пусть

$ qquad displaystyle s_l (z) = sum limits_ {n geq 0} | l cap sigma^n | cdot z^n $

(обычный) генерирующая функция $ l $, т.е. его последовательность количества слов на длину.

Следующее утверждение содержит [FLSE09, p52]:

$ qquad displaystyle l in mathrm {reg} Quad longrightarrow Quad s_l text {rational} $

То есть $ s_l (z) = frac {p (z)} {q (z)} $ с $ p, q $ полиномы.

Итак, любой язык, чья генерирующая функция нет рациональный не регулярно. К сожалению, все линейные языки Также имеют рациональные генерирующие функции », поэтому этот метод не будет работать для более простых нерегулярных языков. Другим недостатком является то, что получение $ s_l $ (и показывает, что это не рационально) может быть тяжелым.

Пример: Рассмотрим язык правильно вложенных слов скобок, т.е. Язык Dyck. Анкет Это генерируется однозначная грамматика

$ qquad displaystyle s to [s] s mid varepsilon $

который можно перевести в уравнение

$ qquad displaystyle s (z) = z^2s^2 (z) + 1 $

одно решение (которое со всеми положительными коэффициентами), из которого

$ qquad displaystyle mathcal {s} (z) = frac {1 - sqrt {1 - 4z^2}} {2z^2} $.

Как $ s_l = mathcal {s} $ [KUIC70] и $ mathcal {s} $ не рационально, язык DYCK не является регулярным.

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

$ $ [FLSE09 Аналитическая комбинаторика П. Флажолет и Р. Седжвик (2009)
$ $ [Kuic70 На энтропии языков без контекста У. Куйч (1970)

Это расширенная версия моего ответа отсюда Использование насосной леммы для доказывания языка $ l = {(01)^m 2^m mid m ge0 } $ не является обычным Поскольку это должен быть справочный вопрос.

Итак, вы думаете, что насосная лемма выглядит сложной? Не волнуйся. Вот несколько иной подход к принятию, который также скрыт в ответе @Romuald. (Викторина: где?)

Давайте начнем с того, что вспомним, что каждый обычный язык принимается детерминированным автоматом конечного состояния (DFA). DFA-это конечный направленный график, где в каждой вершине есть ровно одна внешняя часть для каждой буквы в алфавите. Строки дают вам прогулку на графике, основанном на вершине, помеченной «Start», и DFA принимает, если эта прогулка заканчивается на вершине, помеченной «Принять». (Вершины называются «государствами», потому что разные области математики любят составлять свою собственную терминологию для одного и того же.)

При таком мышлении это легко увидеть: Если строки $ a $ и $ b $ приведут DFA в тот же штат, то для любой другой строки $ c $, $ ac $ и $ bc $ приведет DFA в тот же штат. Почему? Потому что точка заявления о прогулке и строка, определяющая ее, определяют конец полностью.

Положите немного по -другому: Если $ l $ является регулярным, а строки $ $ и $ b $ приводят к тому, что автомат распознавания в одном и том же штате, то для всех строк $ c $ либо $ ac $, так и $ bc $ находятся в $ l $, либо не есть.

Мы можем использовать это, чтобы показать, что языки не регулярно, представляя, что это так, а затем придумывать $ A $ и $ B $, вождение DFA в тот же штат, и $ C $ так, чтобы $ ac $ был на языке и $ BC $ нет. Возьмите пример языка из ответа @Dave. Представьте, что это регулярно, поэтому у него есть некоторое распознавание DFA с государствами $ M $. Принцип Голубиного отверстия гласит, что по крайней мере два из $ {(01)^i: 0 le i le m+1 } $ отправляют DFA в одно и то же состояние, скажем, $ a = (01)^p $ $ b = (01)^Q $. Поскольку $ p neq q $ мы видим, что $ a2^p $ находится на языке, а $ b2^p $ - нет, поэтому этот язык не может быть регулярным.

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

  • Найдите семью строк $ {a_i: i in mathbb {n} } $ с свойством, что у каждого из них есть «хвост» $ t_i $, чтобы $ a_it_i $ находится на языке, а $ a_it_j $, за $ i neq J $ нет.
  • Примените аргумент выше словесного. (Это разрешено, так как всегда достаточно $ a_i $, чтобы позволить вам вызвать принцип голубей.)

Есть и другие трюки, но этот будет легко работать над большинством ваших домашних заданий.

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

После ответа здесь, Я опишу метод доказывания нерегулярности на основе сложности Kolmogorv.

Этот подход обсуждается в «Новый подход к формальной теории языка по сложности Колмогорова», Мин Ли и Пол М.Б. Витани (см. Раздел 3.1).

Пусть $ k (x) $ обозначает сложность Колмогорова строки $ x $, т.е. длину кратчайшего кодирования машины Тьюринга $ m $, так что $ m ( epsilon) = x $ (любое из обычных определений Сделаю). Затем можно использовать следующую лемму, чтобы доказать не регулярность:

КС-Регулярность: Пусть $ l subteq sigma^*$ будет обычным языком, тогда существует постоянная $ c $, которая зависит только от $ l $, так что для всех $ x in sigma^*$, если $ y $ это строка $ n'th $ (относительно лексикографического упорядочения) в $ l_x = left {y in sigma^*| xy in l right } $, затем $ k (y) le o ( log n)+c $.

Можно понять (и доказать) вышеуказанную лемму следующим образом, для любой $ x in sigma^*$, чтобы описать строку $ $ $ в $ l_x $, необходимо указать:

  • Автомат, который принимает $ l $
  • Государство в автомате после обработки префикса $ x $
  • Индекс $ n $

Поскольку нам нужно помнить государство только после обработки $ x $, а не сама $ x $, мы можем скрыть этот фактор в постоянной в зависимости от $ l $. Индекс $ n $ требует для описания битов $ n $, и мы получаем приведенный выше результат (для полноты необходимо добавить конкретные инструкции, необходимые для создания $ y $, но это только добавляет постоянный коэффициент к окончательному описанию )

Эта лемма показывает, как связать сложность Колмогорова всех строк, которые являются членами $ l_x $ для некоторого обычного языка $ l $ и $ x in sigma^*$. Чтобы показать нерегулярность, можно предположить, что $ l $ является регулярным и доказать, что границы слишком ограничительны (например, сложность Kolmogroved для бесконечного набора строк).

Ответ, связанный выше, содержит пример того, как использовать эту лемму, чтобы показать $ l = left {1^p | text {p is rime} right } $ не регулярно, в статье приведено еще несколько примеров. Для полноты, мы показываем здесь, как доказать $ l = left {0^n1^n | n ge 0 right } $ не регулярно.

Учитывая около $ x in left {0,1 right }^*$, мы обозначаем $ y_i^x $ the $ i'Th $ Word в $ l_x $. Обратите внимание, что $ y_1^{0^i} = 1^i $. Используя приведенную выше лемму, сосредоточившись на префиксах $ x $ в форме $ x = 0^i $ и исправляя $ n = 1 $, мы получаем $ forall i ge 0: k (y_1^{0^i}) Le C $. Поскольку $ y_1^{0^i} = 1^i $ это означает, что мы можем связать сложность Колмогорова всех строк формы $ 1^i $ постоянной, что, очевидно, ложное. Стоит отметить, что мы могли бы исследовать один $ x $, например, $ x = 0^n $ для достаточно больших $ n $, что удовлетворяет $ k (0^n) ge log n $ (мы начинаем с высокого уровня Префикс сложности). Поскольку $ y_1^x = 1^n $, мы получаем $ k (1^n)u003Cc$, contradiction (suppose $n> 2^C $).

В случае с унарными языками (языками над алфавитом размера 1) есть простой критерий. Давайте исправим алфавит $ { sigma } $, и для $ a subteq mathbb {n} $, определить $$ l (a) = { sigma^n: n in a }. $$

Теорема. Пусть $ a subteq mathbb {n} $. Следующие эквивалентны:

  1. $ L (а) $ регулярно.

  2. $ L (a) $-это контекстный.

  3. Существует $ n_0, m geq 1 $, так что для всех $ n geq n_0 $ он содержит это $ n in $ iff $ n+m in $. (Мы говорим, что $ a $ - это в конце концов периодически.)

  4. Пусть $ a_i = 1_ {i in a} $. Тогда $ 0.a_0a_1a_2 ldots $ является рациональным.

  5. Функция генерирования $ sum_ {i in a} x^i $ является рациональной функцией.

Теорема может быть доказана во многих отношениях, например, с использованием насосной леммы, теории Myhill -Derode, теоремы Париха, структуры DFA на единых языках (они выглядят как «$ rho $», как в $ rho $ «$ rho $», как в $ rho $ Алгоритм) и так далее. Вот полезное следствие.

Следствие. Пусть $ a subteq mathbb {n} $, и предположим, что $ l (a) $ является регулярным.

  1. Предел $ rho = lim_ {n to infty} frac {| a cap {1, ldots, n } |} {n} $ существует. (Это асимптотическая плотность $ a $.)

  2. Если $ rho = 0 $, то $ a $ конечно.

  3. Если $ rho = 1 $, то $ a $ кофинит (то есть $ overline {a} $ конечен).

Например, язык $ l ( {2^n: n geq 0 }) $ не является обычным, поскольку набор имеет исчезающую асимптотическую плотность, но является бесконечным.

Класс регулярных языков закрывается в рамках различных операций закрытия, таких как союз, пересечение, комплемент, гомоморфизм, регулярная замещение, обратный гомоморфизм и многое другое. Это может быть использовано, чтобы доказать, что заданный язык не является регулярным путем сокращения на язык, который уже известен как нерегулярный.

Как очень простой пример, предположим, что мы знаем, что язык $ {a^nb^n: n geq 0 } $ не регулярно. Тогда мы можем доказать, что язык $ {w in {a, b }^*: #_ a (w) = #_ b (w) } $ (Язык всех слов с одинаково многими $ a $песок $ b $S) не является регулярным следующим образом:

Предположим, что $ L = {w in {a, b }^*: #_ a (w) = #_ b (w) } $ были регулярными. затем $ L cap a^*b^*$ также будет регулярным. Но $ L cap a^* b^* = {a^nb^n: n geq 0 } $, который, как известно, не является регулярным.

Вот более сложный пример. Давайте покажем, что язык $ L '= {(0+1)^n2 (0+1)^n: n geq 0 } $ не регулярно.

Позволять $ H $ быть сопоставлением гомоморфизма, данным $ h (0) = 0 $, $ h (1) = 1 $, $ h (2) = epsilon $. Анкет Если $ L '$ были регулярными, так и был бы следующим языком: $ h (l ' cap 0^*21^*) = {0^n 1^n: n geq 0 } $. Анкет Тем не менее, мы знаем, что последнее не регулярно.

Наконец, вот пример с использованием обратного гомоморфизма. Давайте покажем, что язык $ L '' = {0^n10^n: n geq 0 } $ не обычный.

Позволять $ k $ быть гомоморфизмом, данным $ k (0) = 0 $, $ k (1) = 0 $, $ k (2) = 1 $. Анкет Если $ L '' $ были регулярными, так же бы $ k^{-1} (l '') $ быть, но это просто язык $ L '$ Из предыдущего примера.

Используйте теорию Myhill - Dnerode.

Позволять $ L $ быть языком. Мы говорим, что два слова $ x, y $ находятся неравной модуло $ L $ (или: по отношению к $ L $), если существует слово $ Z $ так что именно один из $ xz, yz $ в $ L $. Анкет В любом DFA для $ L $, $ delta (q_0, x) neq delta (q_0, y) $ (упражнение). Это подразумевает следующий критерий:

Позволять $ L $ быть языком. Предположим, что существует бесконечный набор парных неравенственных слов (то есть бесконечный набор $ S $ так, чтобы любые два неравных $ x, y in s $ являются неравенственными модулем $ L $) затем $ L $ не регулярно.

Вот простой пример применения этого критерия:

Язык $ L = {a^nb^n: n geq 0 } $ не обычный.

Доказательство. Позволять $ S = {a^n: n geq 0 } $. Анкет Мы утверждаем, что любые два разных слова в $ S $ являются неравенственными модулем $ L $. Анкет Действительно, пусть $ a^i, a^j in s $, куда $ i ne j $. Анкет затем $ a^ib^i in l $ но $ a^ib^j notin l $.

Важной особенностью этого метода является то, что он гарантированно будет успешным: если $ L $ не регулярно, тогда существует бесконечный набор парных неравенственных слов. Это следствие Myhill -Dnerode Теорема. Анкет Вкратце, модуло эквивалентности $ L $ (отрицание модуля неравенства $ L $ Определено выше) является отношением эквивалентности и языком $ L $ является регулярным IFF Количество класса эквивалентности модуля эквивалентности $ L $ конечно. Если $ L $ не регулярно, вывод одного слова из каждого классов эквивалентности будут представлять собой бесконечный набор неравенских слов.

Учитывая язык $ L $, для каждой строки $ x $ есть набор струн $ y $ так что $ xy in l $. Анкет Каждый такой набор может быть использован в качестве состояния в государственной машине.

Все, что вам нужно сделать, это показать, что количество таких наборов не является конечным.

В качестве примера, пусть $ L = {a^nb^n: n ≥ 0} $. Анкет Данный $ x = a^nb $ для некоторых $ n ≥ 1 $, единственная строка $ y $ так что $ xy in l $ является $ y = b^{n-1} $. Анкет Так что для каждого $ n $ У нас другой набор, что означает $ L $ не регулярно.

Итак, в целом, если вы найдете бесконечный набор строк $ x $ так что каждый $ x $ дает другой набор $ {y: xy in l } $ тогда язык не может быть распознан конечным государственным машиной и, следовательно, не является регулярным.

Лицензировано под: CC-BY-SA с атрибуция
Не связан с cs.stackexchange
scroll top