Доказательство нерегулярности языков: лемма о разрастании — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 45 промежуточных версий 11 участников)
Строка 1: Строка 1:
'''Лемма о разрастании'''<ref>Лемму также часто называют ''леммой о накачке''.</ref> — лемма, позволяющая во многих случаях проверить, является ли данный язык [[Регулярные языки: два определения и их эквивалентность|регулярным]].
+
'''Лемма о разрастании''' (лемма о накачке, англ. ''pumping lemma'') — лемма, позволяющая во многих случаях проверить, является ли данный язык [[Регулярные языки: два определения и их эквивалентность|регулярным]].
__TOC__
+
== Лемма о разрастании ==
 +
 
 
{{Лемма
 
{{Лемма
 
|id= ==lemma==
 
|id= ==lemma==
|about=о разрастании
+
|about=о разрастании, о накачке
 
|statement=
 
|statement=
 
Пусть <tex>L</tex> — [[Регулярные языки: два определения и их эквивалентность|регулярный язык]] над алфавитом <tex>\Sigma</tex>, тогда существует такое <tex>n</tex>, что для любого слова <tex> \omega \in L</tex> длины не меньше <tex>n</tex> найдутся слова <tex> x,y,z \in \Sigma^*</tex>, для которых верно: <tex>xyz=\omega, y\neq \varepsilon, |xy|\leqslant n</tex> и <tex>\forall k \geqslant 0~xy^{k}z\in L</tex>.
 
Пусть <tex>L</tex> — [[Регулярные языки: два определения и их эквивалентность|регулярный язык]] над алфавитом <tex>\Sigma</tex>, тогда существует такое <tex>n</tex>, что для любого слова <tex> \omega \in L</tex> длины не меньше <tex>n</tex> найдутся слова <tex> x,y,z \in \Sigma^*</tex>, для которых верно: <tex>xyz=\omega, y\neq \varepsilon, |xy|\leqslant n</tex> и <tex>\forall k \geqslant 0~xy^{k}z\in L</tex>.
 
|proof=
 
|proof=
 
[[Файл:Consp_lemma.png||left|240px|]] Пусть <tex>L</tex> — регулярный язык над алфавитом <tex>\Sigma</tex>. Поскольку [[Теорема Клини (совпадение классов автоматных и регулярных языков)|регулярный язык является автоматным]], то найдётся автомат <tex>A</tex>, допускающий язык <tex>L</tex>. Пусть <tex>n</tex> — размер автомата. Докажем, что <tex>n</tex> удовлетворяет условию леммы.
 
[[Файл:Consp_lemma.png||left|240px|]] Пусть <tex>L</tex> — регулярный язык над алфавитом <tex>\Sigma</tex>. Поскольку [[Теорема Клини (совпадение классов автоматных и регулярных языков)|регулярный язык является автоматным]], то найдётся автомат <tex>A</tex>, допускающий язык <tex>L</tex>. Пусть <tex>n</tex> — размер автомата. Докажем, что <tex>n</tex> удовлетворяет условию леммы.
<br/>Возьмём произвольное слово <tex>\omega</tex> длины не меньше <tex>n</tex> из языка <tex>L</tex>. Рассмотрим переходы в автомате <tex>\langle s,\omega\rangle \vdash\langle u_1, \omega[0]^{-1}\omega\rangle\vdash\dots\vdash\langle u_{l},\varepsilon\rangle, \: l\geqslant n</tex>. Так как <tex>l</tex> не меньше количества состояний в автомате <tex>n</tex>, то в переходах будет совпадение. Пусть <tex>u_i</tex> и <tex>u_j</tex> — первое совпадение. Тогда, повторяя участок слова <tex>\omega</tex>, который отвечает за переход от <tex>u_i</tex> к <tex>u_j</tex>, получаем слово, допускаемое автоматом. То есть, если верно <tex>\langle s, xyz\rangle \vdash^*\langle u_i, yz\rangle\vdash^*\langle u_j, z\rangle\vdash^*\langle u_l, \varepsilon\rangle</tex>, то тогда верно <tex>\langle s, xy^kz\rangle \vdash^*\langle u_i, y^kz\rangle\vdash^*\langle u_j, y^{k-1}z\rangle\vdash^*\langle u_j, z\rangle\vdash^*\langle u_l, \varepsilon\rangle</tex>. Тогда автомат <tex>A</tex> допускает слово <tex>xy^kz</tex>, следовательно <tex>xy^kz</tex> принадлежит регулярному языку <tex>L</tex>.  
+
<br/>Возьмём произвольное слово <tex>\omega</tex> длины не меньше <tex>n</tex> из языка <tex>L</tex>. Рассмотрим переходы в автомате <tex>\langle s,\omega\rangle \vdash\langle u_1, \omega[0]^{-1}\omega\rangle\vdash\dots\vdash\langle u_{l},\varepsilon\rangle, \: l\geqslant n</tex>. Так как <tex>l</tex> не меньше количества состояний в автомате <tex>n</tex>, то в переходах будет совпадение. Пусть <tex>u_i</tex> и <tex>u_j</tex> — первое совпадение. Тогда, повторяя участок слова <tex>\omega</tex>, который отвечает за переход от <tex>u_i</tex> к <tex>u_j</tex>, получаем слово, допускаемое автоматом. То есть, если верно <tex>\langle s, xyz\rangle \vdash^*\langle u_i, yz\rangle\vdash^*\langle u_j, z\rangle\vdash^*\langle u_l, \varepsilon\rangle</tex>, то тогда верно <tex>\langle s, xy^kz\rangle \vdash^*\langle u_i, y^kz\rangle\vdash^*\langle u_j, y^{k-1}z\rangle\vdash^*\langle u_j, z\rangle\vdash^*\langle u_l, \varepsilon\rangle</tex>. Тогда автомат <tex>A</tex> допускает слово <tex>xy^kz</tex>, следовательно <tex>xy^kz</tex> принадлежит регулярному языку <tex>L</tex>.<br />
 +
Наконец, поскольку <tex>u_i</tex> и <tex>u_j</tex> — первое совпадение, среди состояний <tex>s, u_1, \ldots, u_i, \ldots, u_{j-1}</tex> нет повторяющихся. Значит, выполняется требование <tex>|xy| \leqslant n</tex>.
 
}}
 
}}
'''Замечание.''' Условие леммы не является достаточным для регулярности языка. ''(См. [[#Пример доказательства без использования леммы|пример 2]])''
+
'''Замечание.''' Условие леммы не является достаточным для регулярности языка. ''(См. [[#Пример нерегулярного языка, для которого выполняется лемма о разрастании|пример]])''
  
== Доказательства нерегулярности языков ==
+
== Лемма о разрастании в общем виде ==
Для доказательства нерегулярности языка можно использовать свойства регулярных и автоматных языков.
+
{{Лемма
<br/>Часто удобно использовать отрицание леммы о разрастании. Пусть <tex>L</tex> — язык над алфавитом <tex>\Sigma</tex>. Если для любого натурального <tex>n</tex> найдётся такое слово <tex>\omega</tex> из данного языка, что его длина будет не меньше <tex> n</tex> и при любом разбиении на три слова <tex>x,y,z</tex> такие, что <tex>y</tex> непустое и длина <tex>xy</tex> не больше <tex>n</tex>, существует такое <tex>k</tex>, что <tex>xy^kz \notin L</tex>, то язык <tex>L</tex> нерегулярный.
+
|id= ==lemma==
=== Пример доказательства с использованием леммы ===
+
|about=о разрастании, о накачке в общем виде
Рассмотрим язык праильных скобочных последовательностей. Для фиксированного <tex>n</tex> предъявляем слово <tex>\omega=(^n)^n</tex>. Пусть <tex>\omega</tex> как-то разбили на <tex>x, y, z</tex>. Так как <tex>|xy|\leqslant n</tex>, то <tex>y=(^b</tex>, где <tex>b > 0</tex>. Для любого такого разбиения берём <tex>k=2</tex> и получаем <tex>xy^kz=(^{n+b})^n</tex>, что не является правильной скобочной последовательностью. Значит, язык правильных скобочных последовательностей нерегулярен.
+
|statement=
=== Пример доказательства без использования леммы ===
+
Если язык <tex>L</tex> является регулярным, то существует число <tex>n \geqslant 1</tex> такое что для любого слова <tex>uwv</tex> из языка <tex>L</tex>, где <tex>|w| \geqslant n</tex> может быть записано в форме <tex>uwv = uxyzv</tex>,
Докажем нерегулярность языка <tex>0^a 1^b 2^b, a \geqslant 1, b \geqslant 0</tex>. Заметим, что здесь условие леммы о накачке выполнено <tex>(n = 1, x = \varepsilon, y = 0)</tex>. Докажем нерегулярность языка с помощью свойств ДКА. Пусть для языка существует автомат <tex>A</tex> c <tex>k</tex> состояниями. Пусть после <tex>a</tex> нулей на вход поступило <tex>k</tex> единиц. При помощи рассуждений, аналогичных приведенным в доказательстве леммы, получаем, что с момента завершения считывания нулей до последнего считывания единицы автомат посетит <tex>k + 1</tex> состояние, т. е. хотя бы в одном из них он окажется дважды. Пусть при первом посещении этого состояния автомат считал <tex>i</tex> единиц, при втором — <tex>j</tex>. Поскольку <tex>0^a 1^i 2^i</tex> принимается автоматом, а <tex>0^a 1^j 2^i</tex> — не принимается, то при подаче автомату, находящемуся в этом состоянии, <tex>i</tex> двоек, автомат, с одной стороны, должен оказаться в допускающем состоянии, с другой — в недопускающем.
+
где слова <tex>x</tex>, <tex>y</tex> и <tex>z</tex> такие, что <tex>|xy| \leqslant n</tex>, <tex>|y| \geqslant 1</tex> и <tex>uxy^izv</tex> принадлежит языку <tex>L</tex> для любого целого числа <tex>i \geqslant 0</tex>.
 +
|proof=
 +
Исходя из формулировки леммы в общем виде, стандартная версия леммы, которая описана выше, является особым случаем, в котором строки <tex>u</tex> и <tex>v</tex> пусты.
 +
Доказательство леммы в общем виде аналогично доказательству стандартной версии леммы, с тем отличием, что строки <tex>u</tex> и <tex>v</tex> теперь могут быть как не пусты, так и пусты.
 +
 
 +
}}
 +
'''Замечание.''' Поскольку лемма в общем виде  накладывает более жесткие требования на язык, то она может быть использована для доказательства нерегулярности многих других языков, таких как <tex> L =\{ a^mb^nc^n : m \geqslant 1 , n \geqslant 1 \}</tex>.
 +
 
 +
== Использование леммы для доказательства нерегулярности языков ==
 +
 
 +
Для доказательства нерегулярности языка часто удобно использовать отрицание леммы о разрастании. Пусть <tex>L</tex> — язык над алфавитом <tex>\Sigma</tex>. Если для любого натурального <tex>n</tex> найдётся такое слово <tex>\omega</tex> из данного языка, что его длина будет не меньше <tex> n</tex> и при любом разбиении на три слова <tex>x,y,z</tex> такие, что <tex>y</tex> непустое и длина <tex>xy</tex> не больше <tex>n</tex>, существует такое <tex>k</tex>, что <tex>xy^kz \notin L</tex>, то язык <tex>L</tex> нерегулярный.
 +
 
 +
Рассмотрим такой подход на примере языка правильных скобочных последовательностей. Для фиксированного <tex>n</tex> предъявляем слово <tex>\omega=(^n)^n</tex>. Пусть <tex>\omega</tex> как-то разбили на <tex>x, y, z</tex>. Так как <tex>|xy|\leqslant n</tex>, то <tex>y=(^b</tex>, где <tex>b > 0</tex>. Для любого такого разбиения берём <tex>k=2</tex> и получаем <tex>xy^kz=(^{n+b})^n</tex>, что не является правильной скобочной последовательностью. Значит, язык правильных скобочных последовательностей нерегулярен.
 +
 
 +
== Пример нерегулярного языка, для которого выполняется лемма о разрастании==
 +
===Пример языка, удовлетворяющего стандартной версии леммы===
 +
Рассмотрим следующий язык: <tex>L= \{ a^{i}b^{j}c^{k} \mid i \ne 1, j \geqslant 0, k \geqslant 0\} \cup \{ ab^{i}c^{i} \mid i \geqslant 1\}</tex>
 +
 
 +
'''Докажем, что он нерегулярный.''' Для этого рассмотрим вспомогательный язык  <tex>L'= \{ ab^{i}c^{i} \mid i \geqslant 1\}</tex> и докажем его нерегулярность. Воспользуемся предложенным в предыдущем пункте подходом. Для фиксированного <tex>n</tex> выберем слово <tex>\omega=ab^nc^n</tex>. Заметим, что при любом разбиении <tex>\omega</tex> на <tex>x, y, z</tex> слово <tex> y </tex> не пусто (по условию леммы) и содержит только символы <tex> a </tex> и <tex> b </tex> (согласно выбранному слову и условию из леммы <tex>|xy|\leqslant n</tex>). Это означает, что при <tex> k = 0 </tex> слово <tex>xy^kz</tex> либо не содержит символа <tex> a </tex>, либо количество символов <tex> b</tex> меньше <tex> n </tex>. В обоих случаях полученное слово не принадлежит языку. Значит язык <tex> L' </tex> нерегулярный.
 +
 
 +
Предположим, что язык <tex> L </tex> регулярный. Заметим, что <tex>L' = L \cap \{ab^{*}c^{*}\} </tex>.  В силу того, что пересечение регулярных языков регулярно, имеем в правой части равенства регулярный язык. При этом в левой части стоит язык, нерегулярность которого была доказана ранее. Значит наше предположение неверно, и язык <tex> L </tex> нерегулярный.
 +
 
 +
'''Докажем, что язык удовлетворяет лемме о разрастании.''' Выберем в лемме <tex> n = 2 </tex>. Это означает, что длина рассматриваемых слов не меньше <tex> 2 </tex> (иными словами <tex> i + j + k \geqslant 2 \,</tex>). Для каждого случая значений <tex> i, j, k </tex> выберем соответствующие слова <tex> x, y </tex> и <tex> z </tex> из леммы. Легко проверить, что в каждом из приведенных ниже случаев условие леммы выполняется:
 +
# <tex> i = 0, j = 0, k \geqslant  2 </tex>. Слово имеет вид <tex>\omega=c^k</tex>. Выберем <tex> x = \varepsilon, y = c, z = c^{k-1}</tex>.
 +
# <tex> i = 0, j \geqslant 1, k \geqslant  0 </tex>. Слово имеет вид <tex>\omega=b^jc^k</tex>. Выберем <tex> x = \varepsilon, y = b, z = b^{j-1}c^k</tex>.
 +
# <tex> i = 1, j \geqslant 1, j = k </tex>. Слово имеет вид <tex>\omega=ab^jc^j</tex>. Выберем <tex> x = \varepsilon, y = a, z = b^jc^j</tex>.
 +
# <tex> i = 2, j \geqslant 1, k \geqslant 1 </tex>. Слово имеет вид <tex>\omega=aab^jc^k</tex>. Выберем <tex> x = \varepsilon, y = aa, z = b^jc^k</tex>.
 +
# <tex> i \geqslant 3, j \geqslant 1, k \geqslant 1 </tex>. Слово имеет вид <tex>\omega=aaaa^{i-3}b^jc^k</tex>. Выберем <tex> x = \varepsilon, y = a, z = aaa^{i-3}b^jc^k</tex>.
 +
 
 +
'''Таким образом''', язык <tex> L </tex> удовлетворяет второй части леммы и при этом является нерегулярным, что доказывает тот факт, что лемма о разрастании '''не''' является достаточным для регулярности языка.
 +
 
 +
===Пример языка, удовлетворяющего лемме в общем виде===
 +
Рассмотрим другой пример.
 +
 
 +
<tex>L_1 =  \{ uvwxy \mid u, y \in \{ 0,1 ,2,3 \}^* \wedge v,w,x \in \{ 0,1,2,3 \} \wedge ( v = w \vee v = x \vee x =w) \}</tex>
 +
 
 +
<tex>L_2 =  \{ w \mid w \in \{ 0,1 ,2,3 \}^* \wedge</tex> <tex>\dfrac{1}{7}</tex> из символов слова <tex>w</tex> является символом <tex>3 \} </tex>
 +
 
 +
<tex>L = L_1 \cup L_2</tex>
 +
 
 +
'''Докажем, что он нерегулярный.''' Предположим, что некоторая строка языка <tex>L</tex> имеет длину <tex>n=5</tex>. Поскольку в алфавите всего четыре символа, то как минимум два символа из пяти в этой строке будут одинаковыми, и они разделены максимум тремя символами:
 +
:Если дубликаты разделены нулями или единицами, накачаем один из двух остальных символов в строке, которые не повлияют на подстроку, которая содержит дубликаты.
 +
:Если дубликаты разделены двойками или тройками, накачаем <tex>2</tex> символа, разделяющих их. Накачка также уменьшает или увеличивает результат во время создания подстроки размера <tex>3</tex>, которая содержит <tex>2</tex> продублированных символа.
 +
Второе условие языка <tex>L</tex> обеспечивает, что <tex>L</tex> — нерегулярный, то есть в нем бесконечное число строк, которые принадлежат <tex>L</tex>, но не могут быть получены путям разрастания некоторой меньшей строки в <tex>L</tex>.
  
 
== См. также ==
 
== См. также ==
 
* [[Лемма о разрастании для КС-грамматик]]
 
* [[Лемма о разрастании для КС-грамматик]]
* [[Интерпретация булевых формул с кванторами как игр для двух игроков]]
+
* [[Булевые формулы с кванторами как игры для двух игроков]]
== Примечания ==
+
 
<references/>
+
== Источники информации ==
== Литература ==
+
* [http://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages Wikipedia — Pumping lemma for regular languages]
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)
+
* Хопкрофт Д., Мотвани Р., Ульман Д. — Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — М.:Издательский дом «Вильямс», 2002. — С. 144. ISBN 5-8459-0261-4
  
 
[[Категория: Теория формальных языков]]
 
[[Категория: Теория формальных языков]]
 
[[Категория: Автоматы и регулярные языки]]
 
[[Категория: Автоматы и регулярные языки]]
 +
[[Категория: Свойства конечных автоматов]]

Текущая версия на 19:28, 4 сентября 2022

Лемма о разрастании (лемма о накачке, англ. pumping lemma) — лемма, позволяющая во многих случаях проверить, является ли данный язык регулярным.

Лемма о разрастании

Лемма (о разрастании, о накачке):
Пусть [math]L[/math]регулярный язык над алфавитом [math]\Sigma[/math], тогда существует такое [math]n[/math], что для любого слова [math] \omega \in L[/math] длины не меньше [math]n[/math] найдутся слова [math] x,y,z \in \Sigma^*[/math], для которых верно: [math]xyz=\omega, y\neq \varepsilon, |xy|\leqslant n[/math] и [math]\forall k \geqslant 0~xy^{k}z\in L[/math].
Доказательство:
[math]\triangleright[/math]
Consp lemma.png
Пусть [math]L[/math] — регулярный язык над алфавитом [math]\Sigma[/math]. Поскольку регулярный язык является автоматным, то найдётся автомат [math]A[/math], допускающий язык [math]L[/math]. Пусть [math]n[/math] — размер автомата. Докажем, что [math]n[/math] удовлетворяет условию леммы.


Возьмём произвольное слово [math]\omega[/math] длины не меньше [math]n[/math] из языка [math]L[/math]. Рассмотрим переходы в автомате [math]\langle s,\omega\rangle \vdash\langle u_1, \omega[0]^{-1}\omega\rangle\vdash\dots\vdash\langle u_{l},\varepsilon\rangle, \: l\geqslant n[/math]. Так как [math]l[/math] не меньше количества состояний в автомате [math]n[/math], то в переходах будет совпадение. Пусть [math]u_i[/math] и [math]u_j[/math] — первое совпадение. Тогда, повторяя участок слова [math]\omega[/math], который отвечает за переход от [math]u_i[/math] к [math]u_j[/math], получаем слово, допускаемое автоматом. То есть, если верно [math]\langle s, xyz\rangle \vdash^*\langle u_i, yz\rangle\vdash^*\langle u_j, z\rangle\vdash^*\langle u_l, \varepsilon\rangle[/math], то тогда верно [math]\langle s, xy^kz\rangle \vdash^*\langle u_i, y^kz\rangle\vdash^*\langle u_j, y^{k-1}z\rangle\vdash^*\langle u_j, z\rangle\vdash^*\langle u_l, \varepsilon\rangle[/math]. Тогда автомат [math]A[/math] допускает слово [math]xy^kz[/math], следовательно [math]xy^kz[/math] принадлежит регулярному языку [math]L[/math].

Наконец, поскольку [math]u_i[/math] и [math]u_j[/math] — первое совпадение, среди состояний [math]s, u_1, \ldots, u_i, \ldots, u_{j-1}[/math] нет повторяющихся. Значит, выполняется требование [math]|xy| \leqslant n[/math].
[math]\triangleleft[/math]

Замечание. Условие леммы не является достаточным для регулярности языка. (См. пример)

Лемма о разрастании в общем виде

Лемма (о разрастании, о накачке в общем виде):
Если язык [math]L[/math] является регулярным, то существует число [math]n \geqslant 1[/math] такое что для любого слова [math]uwv[/math] из языка [math]L[/math], где [math]|w| \geqslant n[/math] может быть записано в форме [math]uwv = uxyzv[/math], где слова [math]x[/math], [math]y[/math] и [math]z[/math] такие, что [math]|xy| \leqslant n[/math], [math]|y| \geqslant 1[/math] и [math]uxy^izv[/math] принадлежит языку [math]L[/math] для любого целого числа [math]i \geqslant 0[/math].
Доказательство:
[math]\triangleright[/math]

Исходя из формулировки леммы в общем виде, стандартная версия леммы, которая описана выше, является особым случаем, в котором строки [math]u[/math] и [math]v[/math] пусты.

Доказательство леммы в общем виде аналогично доказательству стандартной версии леммы, с тем отличием, что строки [math]u[/math] и [math]v[/math] теперь могут быть как не пусты, так и пусты.
[math]\triangleleft[/math]

Замечание. Поскольку лемма в общем виде накладывает более жесткие требования на язык, то она может быть использована для доказательства нерегулярности многих других языков, таких как [math] L =\{ a^mb^nc^n : m \geqslant 1 , n \geqslant 1 \}[/math].

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

Для доказательства нерегулярности языка часто удобно использовать отрицание леммы о разрастании. Пусть [math]L[/math] — язык над алфавитом [math]\Sigma[/math]. Если для любого натурального [math]n[/math] найдётся такое слово [math]\omega[/math] из данного языка, что его длина будет не меньше [math] n[/math] и при любом разбиении на три слова [math]x,y,z[/math] такие, что [math]y[/math] непустое и длина [math]xy[/math] не больше [math]n[/math], существует такое [math]k[/math], что [math]xy^kz \notin L[/math], то язык [math]L[/math] нерегулярный.

Рассмотрим такой подход на примере языка правильных скобочных последовательностей. Для фиксированного [math]n[/math] предъявляем слово [math]\omega=(^n)^n[/math]. Пусть [math]\omega[/math] как-то разбили на [math]x, y, z[/math]. Так как [math]|xy|\leqslant n[/math], то [math]y=(^b[/math], где [math]b \gt 0[/math]. Для любого такого разбиения берём [math]k=2[/math] и получаем [math]xy^kz=(^{n+b})^n[/math], что не является правильной скобочной последовательностью. Значит, язык правильных скобочных последовательностей нерегулярен.

Пример нерегулярного языка, для которого выполняется лемма о разрастании

Пример языка, удовлетворяющего стандартной версии леммы

Рассмотрим следующий язык: [math]L= \{ a^{i}b^{j}c^{k} \mid i \ne 1, j \geqslant 0, k \geqslant 0\} \cup \{ ab^{i}c^{i} \mid i \geqslant 1\}[/math]

Докажем, что он нерегулярный. Для этого рассмотрим вспомогательный язык [math]L'= \{ ab^{i}c^{i} \mid i \geqslant 1\}[/math] и докажем его нерегулярность. Воспользуемся предложенным в предыдущем пункте подходом. Для фиксированного [math]n[/math] выберем слово [math]\omega=ab^nc^n[/math]. Заметим, что при любом разбиении [math]\omega[/math] на [math]x, y, z[/math] слово [math] y [/math] не пусто (по условию леммы) и содержит только символы [math] a [/math] и [math] b [/math] (согласно выбранному слову и условию из леммы [math]|xy|\leqslant n[/math]). Это означает, что при [math] k = 0 [/math] слово [math]xy^kz[/math] либо не содержит символа [math] a [/math], либо количество символов [math] b[/math] меньше [math] n [/math]. В обоих случаях полученное слово не принадлежит языку. Значит язык [math] L' [/math] нерегулярный.

Предположим, что язык [math] L [/math] регулярный. Заметим, что [math]L' = L \cap \{ab^{*}c^{*}\} [/math]. В силу того, что пересечение регулярных языков регулярно, имеем в правой части равенства регулярный язык. При этом в левой части стоит язык, нерегулярность которого была доказана ранее. Значит наше предположение неверно, и язык [math] L [/math] нерегулярный.

Докажем, что язык удовлетворяет лемме о разрастании. Выберем в лемме [math] n = 2 [/math]. Это означает, что длина рассматриваемых слов не меньше [math] 2 [/math] (иными словами [math] i + j + k \geqslant 2 \,[/math]). Для каждого случая значений [math] i, j, k [/math] выберем соответствующие слова [math] x, y [/math] и [math] z [/math] из леммы. Легко проверить, что в каждом из приведенных ниже случаев условие леммы выполняется:

  1. [math] i = 0, j = 0, k \geqslant 2 [/math]. Слово имеет вид [math]\omega=c^k[/math]. Выберем [math] x = \varepsilon, y = c, z = c^{k-1}[/math].
  2. [math] i = 0, j \geqslant 1, k \geqslant 0 [/math]. Слово имеет вид [math]\omega=b^jc^k[/math]. Выберем [math] x = \varepsilon, y = b, z = b^{j-1}c^k[/math].
  3. [math] i = 1, j \geqslant 1, j = k [/math]. Слово имеет вид [math]\omega=ab^jc^j[/math]. Выберем [math] x = \varepsilon, y = a, z = b^jc^j[/math].
  4. [math] i = 2, j \geqslant 1, k \geqslant 1 [/math]. Слово имеет вид [math]\omega=aab^jc^k[/math]. Выберем [math] x = \varepsilon, y = aa, z = b^jc^k[/math].
  5. [math] i \geqslant 3, j \geqslant 1, k \geqslant 1 [/math]. Слово имеет вид [math]\omega=aaaa^{i-3}b^jc^k[/math]. Выберем [math] x = \varepsilon, y = a, z = aaa^{i-3}b^jc^k[/math].

Таким образом, язык [math] L [/math] удовлетворяет второй части леммы и при этом является нерегулярным, что доказывает тот факт, что лемма о разрастании не является достаточным для регулярности языка.

Пример языка, удовлетворяющего лемме в общем виде

Рассмотрим другой пример.

[math]L_1 = \{ uvwxy \mid u, y \in \{ 0,1 ,2,3 \}^* \wedge v,w,x \in \{ 0,1,2,3 \} \wedge ( v = w \vee v = x \vee x =w) \}[/math]

[math]L_2 = \{ w \mid w \in \{ 0,1 ,2,3 \}^* \wedge[/math] [math]\dfrac{1}{7}[/math] из символов слова [math]w[/math] является символом [math]3 \} [/math]

[math]L = L_1 \cup L_2[/math]

Докажем, что он нерегулярный. Предположим, что некоторая строка языка [math]L[/math] имеет длину [math]n=5[/math]. Поскольку в алфавите всего четыре символа, то как минимум два символа из пяти в этой строке будут одинаковыми, и они разделены максимум тремя символами:

Если дубликаты разделены нулями или единицами, накачаем один из двух остальных символов в строке, которые не повлияют на подстроку, которая содержит дубликаты.
Если дубликаты разделены двойками или тройками, накачаем [math]2[/math] символа, разделяющих их. Накачка также уменьшает или увеличивает результат во время создания подстроки размера [math]3[/math], которая содержит [math]2[/math] продублированных символа.

Второе условие языка [math]L[/math] обеспечивает, что [math]L[/math] — нерегулярный, то есть в нем бесконечное число строк, которые принадлежат [math]L[/math], но не могут быть получены путям разрастания некоторой меньшей строки в [math]L[/math].

См. также

Источники информации

  • Wikipedia — Pumping lemma for regular languages
  • Хопкрофт Д., Мотвани Р., Ульман Д. — Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — М.:Издательский дом «Вильямс», 2002. — С. 144. — ISBN 5-8459-0261-4