333
правки
Изменения
→Пример нерегулярного языка, для которого выполняется лемма о разрастании
== Пример нерегулярного языка, для которого выполняется лемма о разрастании==
Рассмотрим следующий язык: <tex>L= \{ a^{i}b^{j}c^{k} \mid i \ge 01, 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> x, y </tex> и <tex> z </tex> из леммы. Легко проверить, что в каждом из приведенных ниже случаев условие леммы выполняется:# <tex> i = 01, j = \ge 1, j = k \ge 1 </tex>. Слово имеет вид <tex>\omega=bcab^jc^kj</tex>. Выберем <tex> x = b\varepsilon, y = c</tex> для любого слова <tex>\omega</tex>. Легко убедитьсяa, что <tex>\forall k \ge 0 ~xyz = b^jc^kz\in Lj</tex>.# <tex> i = 02, j \ge 21, k \ge 1 </tex>. Слово имеет вид <tex>\omega=baab^jc^k</tex>. Выберем <tex> x = \varepsilon, y = aa, z = b^jc^k</tex> для любого слова .# <tex>i \omegage 3, j \ge 1, k \ge 1 </tex>. Легко убедиться, что Слово имеет вид <tex>\forall omega=aaaa^{i-3}b^jc^k </tex>. Выберем <tex> x = \ge 0 ~xyvarepsilon, y = a, z = aaa^{i-3}b^jc^kz\in Lk</tex>.##
== См. также ==
