Изменения

[[#lemma|Лемма]] '''·'''

[[#Доказательства нерегулярности языков|Доказательства нерегулярности языков ]] '''·'''

[[#Литература|Литература]]

|}__NOTOC__

{{Лемма

|id=lemma

|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>xy^{k}z\in L</tex> для всех <tex> k \geqslant 0</tex>.

* [[Лемма о разрастании для КС-грамматик]]

* [[Интерпретация булевых формул с кванторами как игр для двух игроков]]

* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' — '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)

[[Категория: Теория формальных языков]]