Изменения

Рассмотрим следующий язык: <tex>L= \{ a^{i}b^{j}c^{k} \mid i \ge 12, j \ge 1, k \ge 1, \} \cup \{ ab^{i}c^{i} \mid i = \ge 1 \Rightarrow j = k\}</tex>

'''Докажем, что он нерегулярный.''' Для этого рассмотрим вспомогательный язык <tex>L'= \{ ab^{ji}c^{ji} \mid j i \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> нерегулярный.