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> нерегулярный.
'''Докажем, что язык удовлетворяет лемме о разрастании.''' Выберем <tex> n = 2 </tex>. Это означает, что длина рассматриваемых слов не меньше <tex> 2 </tex> (иными словами <tex> i + j + k \ge 2 </tex>). Рассмотрим следующие варианты значений <tex> i, j, k </tex>:
# <tex> i = 0, j = 1, k \ge 1 </tex>. Слово имеет вид <tex>\omega=bc^k</tex>. Выберем <tex> x = b, y = c</tex> для любого слова <tex>\omega</tex>. Легко убедиться, что <tex>\forall k \ge 0 ~xy^kz\in L</tex>.
# <tex> i = 0, j \ge 2, k \ge 1 </tex>. Слово имеет вид <tex>\omega=b^jc^k</tex>. Выберем <tex> x = \varepsilon, y = b</tex> для любого слова <tex>\omega</tex>. Легко убедиться, что <tex>\forall k \ge 0 ~xy^kz\in L</tex>.
#
#
== См. также ==
