76
правок
Изменения
м
→Доказательства нерегулярности языков
== Доказательства нерегулярности языков ==
Для доказательства нерегулярности языка можно использовать свойства регулярных и автоматных языков.
<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 \overline\in 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</tex> больше нуля. Для любого такого разбиения берём <tex>k=2</tex> и получаем <tex>xy^kz=(^{n+b})^n</tex>, что не является правильной скобочной последовательностью. Значит язык правильных скобочных последовательностей не регулярный язык.
=== Нерегулярность языка <tex>\{0^a1^a\}_{a\geqslant 0}</tex> ===
Пусть дан какой-то <tex>n</tex> для него предъявляем слово <tex>\omega=0^n1^n</tex>. После этого слово <tex>\omega</tex> как-то разбили на <tex>x, y, z</tex>. Так как <tex>|xy|\leqslant n</tex>, то из-за выбранного слова <tex>y=0^b</tex>, где <tex>b</tex> больше нуля. Для любого такого разбиения берём <tex>k=2</tex> и получаем <tex>xy^kz=0^{n+b}1^n</tex>, что не является элементом множества слов языка <tex>\{0^a1^a\}_{a\geqslant 0}</tex>, значит этот язык не регулярен.
== См. также ==
* [[Лемма о разрастании для КС-грамматик]]
