Изменения

|statement=

Для каждой [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободный грамматики]] <tex>\Gamma =\langle \Sigma, N, S \in N, P \subset N^{+}\times (\Sigma\cup N)^{*}\rangle</tex> существует такое <tex>n</tex>, что для любого слова <tex>\omega \in L(\Gamma)</tex>, длины не менее <tex>n</tex>, и для любых выделенных в <tex>\omega</tex> не менее <tex>n</tex> позиций, то <tex>\omega</tex> может быть представлено в виде <tex>\omega=uvxyz</tex>, причем:

# <tex>vxy</tex> содержат не более <tex>n</tex> выделенных позиций;

# существует <tex>A \in L</tex>, такой что <tex>S \Rightarrow^{+} uAz \Rightarrow^{+} uvAyz \Rightarrow^{+} uvxyz</tex>

[[Файл:derivation_tree_T.png|240px|thumb|left|Дерево вывода <tex>T</tex>]]Будем называть <tex>v_i</tex> левой ветвящейся вершиной, если ее сын, не принадлежащий пути <tex>v_1, v_2, ..., v_p</tex>, имеет выделенного потомка лежащего слева от <tex>v_p</tex>. В противном случае назовем <tex>v_i</tex> правой ветвящейся вершиной. Рассмотрим последние <tex>2m + 3</tex> вершины принадлежащий пути <tex>v_1, v_2, ..., v_p</tex>. Предположим, что хотя бы <tex>m + 2</tex> вкршины левые ветвящиеся (случай, когда хотя бы <tex>m + 2</tex> вершины правые ветвящиеся, разбирается аналогично). Пусть <tex>u_1, u_2, ..., u_{m + 2}</tex> — последние <tex>m + 2</tex> левые ветвящиеся вершины. Поскольку <tex>m = |N|</tex>, то среди них можно найти как минимум две вершины, соответствующие одному нетерменалу. Обозначим эти вершины <tex>a</tex> и <tex>b</tex>, причем <tex>b</tex> потомок <tex>a</tex>. Тогда на рисунке показано как представить <tex>\omega</tex> в требуемом виде.

}}