333
правки
Изменения
→Пример нерегулярного языка, для которого выполняется лемма о разрастании
== Пример нерегулярного языка, для которого выполняется лемма о разрастании==
Рассмотрим следующий язык: <tex>L= \{ a^{i}b^{j}c^{k} \mid i \ge 0, j \ge 1, k \ge 1, i = 1 \Rightarrow j = k\}</tex>
'''Докажем, что он нерегулярный.''' Для этого рассмотрим вспомогательный язык <tex>L'= \{ ab^{j}c^{j} \mid j \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 L(ab^{*}c^{*}) </tex>. В силу того, что пересечение регулярных языков регулярно, имеем в правой части равенства регулярный язык. При этом в левой части стоит язык, нерегулярность которого была доказана ранее. Значит наше предположение неверно, и язык <tex> L </tex> нерегулярный.
== См. также ==
