«Лемма о накачке»

Пусть $L \ -$ контекстносвободный язык Тогда $\exists \ m,n \in N$ $\forall w \in L \ \ \ |w|≥n$ $\exists \ w = xuyvz$

1. $|uyv| ≤ m$
2. $|uv| \not = 0$

$\forall \ k ≥ 0$ $xu^kyv^kz \ \in \ L$

(максимальная глубина) бинарного дерева: 2^h дерева: M^h

Если дерево имеет высоту $h$ и у каждого узла не больше $M$ сыновей, тогда число листьев не превосходит $M^h$

Доказательство:

Замечание:

<aside> 📌 Если $L \ -$ конечный язык, то доказательство очевидно

</aside>

$L$ $-$ конечное $n = max\{|w|\} +1$

Б.О.О.

$L$ $-$ бесконечен $w \ \in \ L$ $T_w \ -$ самое маленькое по высоте дерево вывода $w$

$L \ -$ контекстносвободный язык $\rArr$ $\exists$ контекстносвободная грамматика $G = (\Sigma, Г, P, S)$ $h = |Г| + 1$ $M = max\{|\alpha| \ \ | \ \ A \to \alpha \ \in \ P\}$ $F = \{w \ \in \ L \ \ | \$ высота $T_w$ не превосходит $h\}$ F - конечное $n = max\{|w| \ \ | \ \ w \ \in \ F\} \ + \ 1$ Пусть $w \ \in \ L$ $|w| ≥ n \rArr$ высота $T_w > h = |Г| + 1$

<aside> 📌 на самом длинном пути, есть хотя бы два повторяющихся нетерминалов.

</aside>

Возьмём самую низкую пару неповторяющихся нетерминалов. (пометка: пара, которая ближе всего к листьями) за $T_1$ обозначим дерево с корнем $A$ ($A$ - сомая верхняя на картинке)

1. Знаем, что высота $T_1$ не превосходит $|Г| + 1$ $\rArr$ в нём не больше $M^{|Г| + 1}$ листьев $\rArr$ $|uyv| ≤ M^{|Г| + 1} = m$
2. $A \rArr^* uAv$ $A \rArr^* y$ пометка: если u и v пустые, то дерево неминимально $k = 0$ $S \rArr^* xAz \rArr^* xyz \rArr xyz$ $\in$ $L$ $k ≥ 1$ $S \rArr^* xAz \rArr^* xu^*Av^z \rArr^ xu^kyv^kz$ $\in$ $L$

#Пример

Доказательство, что $\{a^nb^nc^n \ | \ n≥ 0\}$ не контекстносвободный

Докажем от противного

$L$ $-$ контекстносвободная $\forall \ n, m \in N$ $\exists \ w_{n,m} \in L$ $|w_{n,m}| ≥ n$ $\forall \ w = xuyvz$ $|uyv| ≤ m$ $uv \not = \varepsilon$ $\exists k ≥ 0 \ \ \ \ \ xu^kyv^kz \notin L$