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

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
'''Лемма о разрастании''' (лемма о накачке, англ. ''pumping lemma'') — лемма, позволяющая во многих случаях проверить, является ли данный язык [[Регулярные языки: два определения и их эквивалентность|регулярным]].
+
'''Лемма о разрастании'''<ref>Лемму также часто называют ''леммой о накачке''.</ref>(Pumping lemma) — лемма, позволяющая во многих случаях проверить, является ли данный язык [[Регулярные языки: два определения и их эквивалентность|регулярным]].
 
== Лемма о разрастании ==
 
== Лемма о разрастании ==
  
Строка 15: Строка 15:
  
 
== Лемма о разрастании в общем виде ==
 
== Лемма о разрастании в общем виде ==
{{Лемма
 
|id= ==lemma==
 
|about=о разрастании, о накачке в общем виде
 
|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>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</tex> является регулярным, то существует число <tex>p \geqslant 1</tex> такое что для любого слова <tex>uwv</tex> из языка <tex>L</tex>, где <tex>|w| \geqslant p</tex> может быть записано в форме <tex>uwv = uxyzv</tex>,
'''Замечание.''' Поскольку лемма в общем виде  накладывает более жесткие требования на язык, то она может быть использована для доказательства нерегулярности многих других языков, таких как <tex> L =\{ a^mb^nc^n : m \geqslant 1 , n \geqslant 1 \}</tex>.
+
где слова <tex>x</tex>, <tex>y</tex> и <tex>z</tex> такие, что <tex>|xy| \leqslant p</tex>, <tex>|y| \geqslant 1</tex> и <tex>uxy^izv</tex> принадлежит языку <tex>L</tex> для любого целого числа <tex>i \geqslant 0</tex>.
 +
 
 +
Исходя из этого, стандартная версия леммы, которая описана выше, является особым случаем, в котором строки <tex>u</tex> и <tex>v</tex> пусты.
 +
 
 +
Поскольку лемма в общем виде  накладывает более жесткие требования на язык, то она может быть использована для доказательства нерегулярности многих других языков, таких как <tex> L =\{ a^mb^nc^n : m \geqslant 1 , n \geqslant 1 \}</tex>.
  
 
== Использование леммы для доказательства нерегулярности языков ==
 
== Использование леммы для доказательства нерегулярности языков ==
Строка 35: Строка 30:
  
 
== Пример нерегулярного языка, для которого выполняется лемма о разрастании==
 
== Пример нерегулярного языка, для которого выполняется лемма о разрастании==
===Пример языка, удовлетворяющего стандартной версии леммы===
 
 
Рассмотрим следующий язык: <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= \{ 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'= \{ ab^{i}c^{i} \mid i \ge 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> 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> 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 = 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 = 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>.
Строка 51: Строка 45:
 
'''Таким образом''', язык <tex> L </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_1 =  \{ uvwxy \mid u, y \in \{ 0,1 ,2,3 \}^*; 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_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 = L_1 \cup L_2</tex>
  
'''Докажем, что он нерегулярный.''' Предположим, что некоторая строка языка <tex>L</tex> имеет длину <tex>n=5</tex>. Поскольку в алфавите всего четыре символа, то как минимум два символа из пяти в этой строке будут одинаковыми, и они разделены максимум тремя символами:
+
Предположим, что некоторая строка языка <tex>L</tex> имеет длину пять. Поскольку в алфавите всего четыре символа, то как минимум два символа из пяти в этой строке будут одинаковыми, и они разделены максимум тремя символами:
:Если дубликаты разделены нулями или единицами, накачаем один из двух остальных символов в строке, которые не повлияют на подстроку, которая содержит дубликаты.
+
:Если дубликаты разделены нулями или единицами, накачаем один из двух остальных символов в строке, которые не повлияют на подстроку, которая содержит дубликаты,
:Если дубликаты разделены двойками или тройками, накачаем <tex>2</tex> символа, разделяющих их. Накачка также уменьшает или увеличивает результат во время создания подстроки размера <tex>3</tex>, которая содержит <tex>2</tex> продублированных символа.
+
:Если дубликаты разделены двойками или тройками, накачаем 2 символа, разделяющих их. Накачка также уменьшает или увеличивает результат во время создания подстроки размера 3, которая содержит 2 продублированных символа
Второе условие языка <tex>L</tex> обеспечивает, что <tex>L</tex> нерегулярный, то есть в нем бесконечное число строк, которые принадлежат <tex>L</tex>, но не могут быть получены путям разрастания некоторой меньшей строки в <tex>L</tex>.
+
Второе условие языка <tex>L</tex> обеспечивает, что <tex>L</tex> - нерегулярный, то есть в нем бесконечное число строк, которые принадлежат <tex>L</tex>, но не могут быть получены путям разрастания некоторой меньшей строки в <tex>L</tex>
  
 
== См. также ==
 
== См. также ==
 
* [[Лемма о разрастании для КС-грамматик]]
 
* [[Лемма о разрастании для КС-грамматик]]
* [[Булевые формулы с кванторами как игры для двух игроков]]
+
* [[Интерпретация булевых формул с кванторами как игр для двух игроков]]
 
+
== Примечания ==
== Источники информации ==
+
<references/>
 +
== Источники ==
 +
* Хопкрофт Д., Мотвани Р., Ульман Д. — Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — М.:Издательский дом «Вильямс», 2002. — С. 144. — ISBN 5-8459-0261-4
 
* [http://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages Wikipedia — Pumping lemma for regular languages]
 
* [http://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages Wikipedia — Pumping lemma for regular languages]
* Хопкрофт Д., Мотвани Р., Ульман Д. — Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — М.:Издательский дом «Вильямс», 2002. — С. 144. — ISBN 5-8459-0261-4
 
  
 
[[Категория: Теория формальных языков]]
 
[[Категория: Теория формальных языков]]
 
[[Категория: Автоматы и регулярные языки]]
 
[[Категория: Автоматы и регулярные языки]]
[[Категория: Свойства конечных автоматов]]
 

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблон, используемый на этой странице: