Доказ нерегулярності мов лема про розростання
Лема про розростання(лема про накачування, англ.pumping lemma) — лема, що дозволяє у багатьох випадках перевірити, чи ця мова є регулярною.
Зміст
Лемма про розростання [ред.]
| Лемма (про розростання, про накачування): |
| Нехай [math]L[/math] — регулярна мова над алфавітом [math]\Sigma[/math] , тоді існує таке [math]n[/math] , що для будь-якого слова [math] \omega \in L[/ math] довжини не менше [math]n[/math] знайдуться слова [math] x,y,z \in \Sigma^*[/math] , для яких вірно: [math]xyz=\omega, y\neq \ varepsilon, xy\leqslant n[/math] та [math]\forall k \geqslant 0 |
xy^z\in L[/math] .
Візьмемо довільне слово [math]\omega[/math] довжини не менше [math]n[/math] з мови [math]L[/math]. Розглянемо переходи в автоматі [math] \ langle s, \ omega \ rangle \ vdash \ langle u_1, \ omega [0] ^ \ omega \ rangle \ vdash \ dots \ vdash \ langle u_, \ varepsilon \ rangle, \: l \ geqslant n[/math] . Оскільки [math]l[/math] не менше кількості станів в автоматі [math]n[/math] , то переходах буде збіг. Нехай [math]u_i[/math] і [math]u_j[/math] - перший збіг. Тоді, повторюючи ділянку слова [math]\omega[/math] , що відповідає за перехід від [math]u_i[/math] до [math]u_j[/math] , отримуємо слово, яке допускається автоматично. Тобто, якщо вірно [math]\langle s, xyz\rangle \vdash^*\langle u_i, yz\rangle\vdash^*\langle u_j, z\rangle\vdash^*\langle u_l, \varepsilon\rangle[ /math] , то тоді вірно [math]\langle s, xy^kz\rangle \vdash^*\langle u_i, y^kz\rangle\vdash^*\langle u_j, y^z\rangle\vdash^*\ langle u_j,z\rangle\vdash^*\langle u_l, \varepsilon\rangle[/math] . Тоді автомат [math]A[/math] допускає слово [math]xy^kz[/math] , отже [math]xy^kz[/math] належить регулярній мові [math]L[/math] .
Нарешті, оскільки [math]u_i[/math] і [math]u_j[/math] - перший збіг, серед станів [math]s, u_1, \ldots, u_i, \ldots, u_[/math] немає повторюваних. Отже, виконується вимога [math] xy \ leqslant n [/ math].
Зауваження.Умова леми не є достатньою для регулярності мови.(Див. приклад)
Лемма про розростання у загальному вигляді [ред.]
| Лемма (про розростання, про накачування в загальному вигляді): |
| Якщо мова [math]L[/math] є регулярною, то існує число [math]n \geqslant 1[/math] таке, що для будь-якого слова [math]uwv[/math] з мови [math]L[/math] , де [math]w \geqslant n[/math] може бути записано у формі [math]uwv = uxyzv[/math] , де слова [math]x[/math] , [math]y[/math] та [ math]z[/math] такі, що [math]xy \leqslant n[/math] , [math]y \geqslant 1[/math] та [math]uxy^izv[/math] належить мові [math]L [/math] для будь-якого цілого числа [math]i \geqslant 0[/math] . |
| Доказ: |
| [math]\triangleright[/math] |
| [math]\triangleleft[/math] |
Зауваження.Оскільки лема взагальному вигляді накладає більш жорсткі вимоги на мову, вона може бути використана для доказу нерегулярності багатьох інших мов, таких як [math] L =\< a^mb^nc^n : m \geqslant 1 , n \geqslant 1 \>[/math] .
Використання леми для доказу нерегулярності мов [ред.]
Для доказу нерегулярності мови часто зручно використовувати заперечення леми про розростання. Нехай [math] L [/ math] - мова над алфавітом [ math] \ Sigma [/ math]. Якщо для будь-якого натурального [math]n[/math] знайдеться таке слово [math]\omega[/math] з даної мови, що його довжина буде не менше [math] n[/math] і за будь-якого розбиття на три слова [ math]x,y,z[/math] такі, що [math]y[/math] непусте і довжина [math]xy[/math] не більше [math]n[/math] існує таке [math]k [/math] , що [math]xy^kz \notin L[/math] , то мова [math]L[/math] нерегулярний.
Розглянемо такий підхід з прикладу мови правильних дужних послідовностей. Для фіксованого [math]n[/math] висуваємо слово [math]\omega=(^n)^n[/math] . Нехай [math]\omega[/math] якось розбили на [math]x, y, z[/math]. Оскільки [math]xy\leqslant n[/math] , то [math]y=(^b[/math] , де [math]b \gt 0[/math] . Для будь-якого такого розбиття беремо [math]k =2[/math] і отримуємо [math]xy^kz=(^)^n[/math] , що не є правильною скобковою послідовністю.
Приклад нерегулярної мови, для якої виконується лема про розростання [ред.]
Приклад мови, що відповідає стандартній версії леми [ ред. ]
Розглянемо таку мову: [math]L= \< a^b^c^ \mid i \ne 1, j \geqslant 0, k \geqslant 0\> \cup \< ab^c^\mid i \geqslant 1\>[/math]
Доведемо, що він нерегулярний.Для цього розглянемо допоміжну мову [math] L'= \< ab^c^\mid i \geqslant 1\/gt;[/math] і доведемо його нерегулярність. Скористаємося запропонованим у попередньому пункті підходом. Для фіксованого [math]n[/math] виберемо слово [math]\omega=ab^nc^n[/math] . Зауважимо, що за будь-якого розбиття [math]\omega[/math] на [math]x, y, z[/math] слово [math] y [/math] не порожнє (за умовою леми) і містить лише символи [math] ] a [/math] і [math] b [/math] (згідно з вибраним словом і умовою з леми [math]xy\leqslant n[/math] ). Це означає, що з [math] k = 0 [/math] слово [math]xy^kz[/math] або містить символу [math] a [/math] , або кількість символів [math] b[/math] менше [math] n [/math] . В обох випадках отримане слово не належить до мови. Значить мова [math] L' [/math] нерегулярна.
Припустимо, що мова [math] L [/math] регулярна. Зауважимо, що [math]L' = L \cap \c^\> [/ Math] . Через те, що перетин регулярних мов регулярно, маємо у правій частині рівності регулярну мову. При цьому в лівій частині стоїть мова, нерегулярність якої була доведена раніше. Значить, наше припущення неправильне, і мова [math] L [/math] нерегулярна.
Доведемо, що мова задовольняє лемі про розростання.Виберемо в лемі [math] n = 2 [/math] . Це означає, що довжина слів, що розглядаються, не менше [math] 2 [/math] (іншими словами [math] i + j + k \geqslant 2 \,[/math] ). До кожного випадку значень [math] i, j, k [/math] виберемо відповідні слова [math] x, y [/math] і [math] z [/math] з леми. Легко перевірити, що в кожному з наведених нижче випадків умова леми виконується:
- [math] i = 0, j = 0, k \ geqslant 2 [/math] . Слово має вигляд [math]\omega=c^k[/math] . Виберемо [math] x = \varepsilon, y = c, z = c^[/math].
- [math] i = 0, j \geqslant 1, k \geqslant 0 [/math] . Слово має вигляд [math]\omega=b^jc^k[/math] . Виберемо [math] x = \varepsilon, y = b, z = b^c^k[/math].
- [math] i = 1, j \ geqslant 1, j = k [/math] . Слово має вигляд [math]\omega=ab^jc^j[/math] . Виберемо [math] x = \varepsilon, y = a, z = b^jc^j[/math].
- [math] i = 2, j \geqslant 1, k \geqslant 1 [/math] . Слово має вигляд [math]\omega=aab^jc^k[/math] . Виберемо [math] x = \varepsilon, y = aa, z = b^jc^k[/math].
- [math] i \geqslant 3, j \geqslant 1, k \geqslant 1 [/math]. Слово має вигляд [math]\omega=aaaa^b^jc^k[/math] . Виберемо [math] x = \varepsilon, y = a, z = aaa^b^jc^k[/math] .
Таким чином, мова [math] L [/math] задовольняє другої частини леми і при цьому є нерегулярною, що доводить той факт, що лема про розростаннянеє достатньою для регулярності мови.
Приклад мови, що задовольняє лемі в загальному вигляді [ред.]
Розглянемо інший приклад.
[math]L_2 = \< w \mid w \in \< 0,1 ,2,3 \>^* \wedge[/math] [math]\dfrac[/math] із символів слова [math]w[/math] є символом [math]3 \> [/math]
[math]L = L_1 \cup L_2[/math]
Доведемо, що він нерегулярний.Припустимо, що деякий рядок мови [math]L[/math] має довжину [math]n=5[/math] . Оскільки в алфавіті всього чотири символи, то як мінімум два символи з п'яти в цьому рядку будуть однаковими, і вони розділені максимум трьома символами:
Якщо дублікати розділені нулями або одиницями, накачаємо один із двох інших символів у рядку, які не вплинуть на підрядок, що містить дублікати. Якщо дублікати розділені двійками або трійками, накачаємо [math]2[/math] символи, що їх розділяють. Накачування також зменшує абозбільшує результат під час створення підрядки розміру [math]3[/math] , яка містить [math]2[/math] продубльованого символу.
Друга умова мови [math]L[/math] забезпечує, що [math]L[/math] — нерегулярна, тобто в ній нескінченна кількість рядків, які належать [math]L[/math] , але не можуть бути отримані шляхом розростання деякого меншого рядка [math]L[/math] .