Использование леммы прокачки для доказательства языка не является регулярным

Я пытаюсь использовать насосную лемму, чтобы доказать, что не является регулярным.$L = \{(01)^m 2^m \mid m \ge0\}$

Это то, что я имею до сих пор: Предположим, что регулярна, и пусть будет длиной накачки, поэтому . Рассмотрим любое накачанное разложение такое, что и .p w = ( 01 ) p 2 $L$$p$$w = (01)^p 2^p$| у | > 0 | х у | ≤ $w = xyz$$|y| >0$$|xy| \le p$

Я не уверен, что делать дальше.

Я на правильном пути? Или я далеко?

Подсказка: вам нужно рассмотреть, как выглядят все разложения , так что все возможные вещи , и могут быть заданы так, что . Затем вы прокачиваете каждый из них и видите, нет ли у вас противоречия, которое будет словом не на вашем языке. Каждый случай должен привести к противоречию, которое тогда будет противоречием леммы о накачке. Вуаля! Язык не будет регулярным.x y z x y z = ( 01 ) p 2 $w=xyz$$x$$y$$z$$xyz=(01)^p2^p$

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

У вас есть разложение и ограничение длины | х у | ≤ р . Что это говорит о том , как x , y и z могут вписаться в разложение? В частности, лемма прокачки позволяет вам повторять y , поэтому ваша цель состоит в том, чтобы найти способ, которым многократное повторение y (или удаление y , иногда это проще) бесповоротно возмущает шаблон, который определяет язык.$xyz = (01)^p 2^p$$|xy| \le p$$x$$y$$z$$y$$y$$y$

В шаблоне есть очевидная граница: первая часть содержит повторения , вторая часть содержит только 2 . Интересно, где у падает. Есть у всегда содержится в одной из этих частей, или она может колебаться два?$01$$2$$y$$y$

Так как , x y полностью содержится в части ( 01 ) p , а z содержит все 2 . Поэтому, если вы повторите y еще раз, вы получите более длинную первую часть, но часть 2 p останется прежней. Другими словами, x y y z оканчивается ровно p буквами 2 . Чтобы правильно завершить доказательство, покажите, что x y y z содержит слишком много букв 0 и $|xy| \le p$$xy$$(01)^p$$z$$2$$y$$2^p$$xyyz$$p$$2$$xyyz$$0$$1$ чтобы соответствовать регулярному выражению.

Три года спустя мы собираемся доказать, что с Δ = { 0 , 1 , 2 } не является регулярным, в отличие от использования свойств замыкания (более быстрый способ, чем использование леммы о накачке). ).$L = \{(01)^m 2^m \mid m \ge0\}$$\Delta=\{0,1,2\}$

Сначала предположим, что регулярно. Мы знаем, что регулярные языки замкнуты при обратном гомоморфизме.$L$

Рассмотрим гомоморфизм с:$h:\Sigma^* \rightarrow \Delta^*$

$\Sigma = \{a,b\}$

$h(a)= 01$

$h(b)= 2$

Обратный гомоморфизм равен:$L$

$h^{-1}(L)= \{a^nb^n| n\geq 0 \} = L'$

Это порождает противоречие, поскольку является каноническим примером нерегулярного языка, поэтому L не может быть регулярным.$L'$$L$

Я собираюсь дать не ответ на этот вопрос, поскольку это не совсем лемма накачки, но, возможно, проливает свет на идею леммы накачки. Вот основной факт о детерминированных автоматах конечного состояния, который является сущностью теоремы Майхилла-Нерода: если две строки и b переводят FSA в одно и то же состояние, то для любого c оба из a c и b c равны принято или нет.$a$$b$$c$$ac$$bc$

Возвращаясь к вашей проблеме, предположим, что у детерминированного автомата для вашего языка есть состояний. Тогда по крайней мере два из ( 01 ) 1 , ( 01 ) 2 , ... , ( 01 ) п + 1 , скажем ( 01 ) р и ( 01 ) д с р ≠ д , привод автомат в то же состояние (это принцип голубиного отверстия). В соответствии с фактом, то либо оба ( 01 ) р 2 р и$n$$(01)^1$$(01)^2$$\ldots$$(01)^{n+1}$$(01)^p$$(01)^q$$p\neq q$$(01)^p2^p$ в L или нет, что противоречит.$(01)^q2^p$$L$