Доказательство нерегулярности языков: лемма о разрастании — различия между версиями
Ateuhh (обсуждение | вклад) (→Пример языка, удовлетворяющего лемме в общем виде) |
|||
(не показано 14 промежуточных версий 3 участников) | |||
Строка 1: | Строка 1: | ||
− | '''Лемма о разрастании''' | + | '''Лемма о разрастании''' (лемма о накачке, англ. ''pumping lemma'') — лемма, позволяющая во многих случаях проверить, является ли данный язык [[Регулярные языки: два определения и их эквивалентность|регулярным]]. |
== Лемма о разрастании == | == Лемма о разрастании == | ||
Строка 19: | Строка 19: | ||
|about=о разрастании, о накачке в общем виде | |about=о разрастании, о накачке в общем виде | ||
|statement= | |statement= | ||
− | Если язык <tex>L</tex> является регулярным, то существует число <tex> | + | Если язык <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 | + | где слова <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= | |proof= | ||
Исходя из формулировки леммы в общем виде, стандартная версия леммы, которая описана выше, является особым случаем, в котором строки <tex>u</tex> и <tex>v</tex> пусты. | Исходя из формулировки леммы в общем виде, стандартная версия леммы, которая описана выше, является особым случаем, в котором строки <tex>u</tex> и <tex>v</tex> пусты. | ||
Строка 26: | Строка 26: | ||
}} | }} | ||
− | '''Замечание.'''Поскольку лемма в общем виде накладывает более жесткие требования на язык, то она может быть использована для доказательства нерегулярности многих других языков, таких как <tex> L =\{ a^mb^nc^n : m \geqslant 1 , n \geqslant 1 \}</tex>. | + | '''Замечание.''' Поскольку лемма в общем виде накладывает более жесткие требования на язык, то она может быть использована для доказательства нерегулярности многих других языков, таких как <tex> L =\{ a^mb^nc^n : m \geqslant 1 , n \geqslant 1 \}</tex>. |
== Использование леммы для доказательства нерегулярности языков == | == Использование леммы для доказательства нерегулярности языков == | ||
Строка 38: | Строка 38: | ||
Рассмотрим следующий язык: <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 \ | + | '''Докажем, что он нерегулярный.''' Для этого рассмотрим вспомогательный язык <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> 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>. | ||
Строка 60: | Строка 60: | ||
<tex>L = L_1 \cup L_2</tex> | <tex>L = L_1 \cup L_2</tex> | ||
− | '''Докажем, что он нерегулярный.''' Предположим, что некоторая строка языка <tex>L</tex> имеет длину | + | '''Докажем, что он нерегулярный.''' Предположим, что некоторая строка языка <tex>L</tex> имеет длину <tex>n=5</tex>. Поскольку в алфавите всего четыре символа, то как минимум два символа из пяти в этой строке будут одинаковыми, и они разделены максимум тремя символами: |
− | :Если дубликаты разделены нулями или единицами, накачаем один из двух остальных символов в строке, которые не повлияют на подстроку, которая содержит дубликаты | + | :Если дубликаты разделены нулями или единицами, накачаем один из двух остальных символов в строке, которые не повлияют на подстроку, которая содержит дубликаты. |
− | :Если дубликаты разделены двойками или тройками, накачаем 2 символа, разделяющих их. Накачка также уменьшает или увеличивает результат во время создания подстроки размера 3, которая содержит 2 продублированных символа | + | :Если дубликаты разделены двойками или тройками, накачаем <tex>2</tex> символа, разделяющих их. Накачка также уменьшает или увеличивает результат во время создания подстроки размера <tex>3</tex>, которая содержит <tex>2</tex> продублированных символа. |
− | Второе условие языка <tex>L</tex> обеспечивает, что <tex>L</tex> | + | Второе условие языка <tex>L</tex> обеспечивает, что <tex>L</tex> — нерегулярный, то есть в нем бесконечное число строк, которые принадлежат <tex>L</tex>, но не могут быть получены путям разрастания некоторой меньшей строки в <tex>L</tex>. |
== См. также == | == См. также == | ||
* [[Лемма о разрастании для КС-грамматик]] | * [[Лемма о разрастании для КС-грамматик]] | ||
− | * [[ | + | * [[Булевые формулы с кванторами как игры для двух игроков]] |
− | == | + | |
− | + | == Источники информации == | |
− | + | * [http://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages Wikipedia — Pumping lemma for regular languages] | |
* Хопкрофт Д., Мотвани Р., Ульман Д. — Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — М.:Издательский дом «Вильямс», 2002. — С. 144. — ISBN 5-8459-0261-4 | * Хопкрофт Д., Мотвани Р., Ульман Д. — Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — М.:Издательский дом «Вильямс», 2002. — С. 144. — ISBN 5-8459-0261-4 | ||
− | |||
[[Категория: Теория формальных языков]] | [[Категория: Теория формальных языков]] | ||
[[Категория: Автоматы и регулярные языки]] | [[Категория: Автоматы и регулярные языки]] | ||
[[Категория: Свойства конечных автоматов]] | [[Категория: Свойства конечных автоматов]] |
Текущая версия на 09:24, 14 марта 2018
Лемма о разрастании (лемма о накачке, англ. pumping lemma) — лемма, позволяющая во многих случаях проверить, является ли данный язык регулярным.
Содержание
Лемма о разрастании[править]
Лемма (о разрастании, о накачке): |
Пусть регулярный язык над алфавитом , тогда существует такое , что для любого слова длины не меньше найдутся слова , для которых верно: и . — |
Доказательство: |
Пусть — регулярный язык над алфавитом . Поскольку регулярный язык является автоматным, то найдётся автомат , допускающий язык . Пусть — размер автомата. Докажем, что удовлетворяет условию леммы.
|
Замечание. Условие леммы не является достаточным для регулярности языка. (См. пример)
Лемма о разрастании в общем виде[править]
Лемма (о разрастании, о накачке в общем виде): |
Если язык является регулярным, то существует число такое что для любого слова из языка , где может быть записано в форме ,
где слова , и такие, что , и принадлежит языку для любого целого числа . |
Доказательство: |
Исходя из формулировки леммы в общем виде, стандартная версия леммы, которая описана выше, является особым случаем, в котором строки Доказательство леммы в общем виде аналогично доказательству стандартной версии леммы, с тем отличием, что строки и пусты. и теперь могут быть как не пусты, так и пусты. |
Замечание. Поскольку лемма в общем виде накладывает более жесткие требования на язык, то она может быть использована для доказательства нерегулярности многих других языков, таких как
.Использование леммы для доказательства нерегулярности языков[править]
Для доказательства нерегулярности языка часто удобно использовать отрицание леммы о разрастании. Пусть
— язык над алфавитом . Если для любого натурального найдётся такое слово из данного языка, что его длина будет не меньше и при любом разбиении на три слова такие, что непустое и длина не больше , существует такое , что , то язык нерегулярный.Рассмотрим такой подход на примере языка правильных скобочных последовательностей. Для фиксированного
предъявляем слово . Пусть как-то разбили на . Так как , то , где . Для любого такого разбиения берём и получаем , что не является правильной скобочной последовательностью. Значит, язык правильных скобочных последовательностей нерегулярен.Пример нерегулярного языка, для которого выполняется лемма о разрастании[править]
Пример языка, удовлетворяющего стандартной версии леммы[править]
Рассмотрим следующий язык:
Докажем, что он нерегулярный. Для этого рассмотрим вспомогательный язык
и докажем его нерегулярность. Воспользуемся предложенным в предыдущем пункте подходом. Для фиксированного выберем слово . Заметим, что при любом разбиении на слово не пусто (по условию леммы) и содержит только символы и (согласно выбранному слову и условию из леммы ). Это означает, что при слово либо не содержит символа , либо количество символов меньше . В обоих случаях полученное слово не принадлежит языку. Значит язык нерегулярный.Предположим, что язык
регулярный. Заметим, что . В силу того, что пересечение регулярных языков регулярно, имеем в правой части равенства регулярный язык. При этом в левой части стоит язык, нерегулярность которого была доказана ранее. Значит наше предположение неверно, и язык нерегулярный.Докажем, что язык удовлетворяет лемме о разрастании. Выберем в лемме
. Это означает, что длина рассматриваемых слов не меньше (иными словами ). Для каждого случая значений выберем соответствующие слова и из леммы. Легко проверить, что в каждом из приведенных ниже случаев условие леммы выполняется:- . Слово имеет вид . Выберем .
- . Слово имеет вид . Выберем .
- . Слово имеет вид . Выберем .
- . Слово имеет вид . Выберем .
- . Слово имеет вид . Выберем .
Таким образом, язык
удовлетворяет второй части леммы и при этом является нерегулярным, что доказывает тот факт, что лемма о разрастании не является достаточным для регулярности языка.Пример языка, удовлетворяющего лемме в общем виде[править]
Рассмотрим другой пример.
из символов слова является символом
Докажем, что он нерегулярный. Предположим, что некоторая строка языка
имеет длину . Поскольку в алфавите всего четыре символа, то как минимум два символа из пяти в этой строке будут одинаковыми, и они разделены максимум тремя символами:- Если дубликаты разделены нулями или единицами, накачаем один из двух остальных символов в строке, которые не повлияют на подстроку, которая содержит дубликаты.
- Если дубликаты разделены двойками или тройками, накачаем символа, разделяющих их. Накачка также уменьшает или увеличивает результат во время создания подстроки размера , которая содержит продублированных символа.
Второе условие языка
обеспечивает, что — нерегулярный, то есть в нем бесконечное число строк, которые принадлежат , но не могут быть получены путям разрастания некоторой меньшей строки в .См. также[править]
Источники информации[править]
- Wikipedia — Pumping lemma for regular languages
- Хопкрофт Д., Мотвани Р., Ульман Д. — Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — М.:Издательский дом «Вильямс», 2002. — С. 144. — ISBN 5-8459-0261-4