editor
143
правки
Изменения
Нет описания правки
# существует <tex>A \in L</tex>, такой что <tex>S \Rightarrow^{+} uAz \Rightarrow^{+} uvAyz \Rightarrow^{+} uvxyz</tex>.
|proof=
Введем следующие обозначения: <tex>m = |N|</tex> и <tex>l</tex> — длина самой длинной правой части правила из <tex>P</tex>. Тогда в качестве <tex>n</tex> возьмем <tex>l^{2m + 3}</tex>. Рассмотрим дерево разбора <tex>T</tex> для произвольного слова <tex>\omega \in L(\Gamma)</tex>, у которого <tex>|\omega| \ge n</tex>. В силу выбора <tex>n</tex> в <tex>T</tex> будет по крайне мере один путь от корня до листа длины, не менее <tex>2m + 3</tex>. Произвольным образом выделим в <tex>\omega</tex> не менее <tex>n</tex> позиций. Соответствующие этим позициям листья дерева <tex>T</tex> будем называть выделенными.
Пусть <tex>v_1</tex> — корень <tex>T</tex>, а <tex>v_{i + 1}</tex> — сын <tex>v_i</tex>, который имеет среди своих потомков наибольшее число выделенных листьев (если таких несколько, то <tex>v_{i + 1}</tex> самый правый из них). Рассмотрим <tex>v_1, v_2, ..., v_p</tex> — путь от корня до листа.
Будем называть ветвящейся ту вершину, у которой по крайне мере два сына имеют выделенных потомков. Докажем по индукции, что если среди <tex>v_1, v_2, ..., v_i</tex> вершин есть <tex>k</tex> ветвящихся, то <tex>v_{i + 1}</tex> имеет хотя бы <tex>l^{2m + 3 - k}</tex> выделенных потомков. <br>База индукции: <tex>i = 0</tex>. Тогда <tex>k = 0</tex> и <tex>v_1</tex> имеет по крайне мере <tex>n</tex> выделенных потомков, поскольку является корнем. <br>Индукционный переход. Если <tex>v_i</tex> не является ветвящейся вершиной, то <tex>v_{i + 1}</tex> имеет такое же число ветвящихся потомков , как и <tex>v_i</tex>. Если <tex>v_i</tex> — ветвящаяся вершина, то <tex>v_{i + 1}</tex> имеет не более чем в <tex>l</tex> раз меньшее число выделенных потомков.
Поскольку <tex>v_1</tex> имеет хотя бы <tex>n = l^{2m + 3}</tex> выделенных потомков, то <tex>v_1, v_2, ..., v_p</tex> содержит по крайне мере <tex>2m + 3</tex> ветвящиеся вершин. Заметим, что <tex>v_p</tex> — лист, поэтому <tex>p > 2m + 3</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> в требуемом виде.
Условие (1) выполнено, поскольку <tex>x</tex> содержит выделенную вершину, а именно <tex>v_p</tex>. Очевидно, что условие (4) выполнено в силу предложенного разбиения <tex>\omega</tex>. Кроме того, <tex>u</tex> содержит выделенную вершину, а именно потомка некоторого сына вершины <tex>u_1</tex>. Аналогично, выделенный потомок некоторого сына вершины <tex>a</tex> содержится в <tex>v</tex>. Таким образом, условие (2) выполнено. Поскольку между <tex>v_p</tex> и <tex>a</tex> не более <tex>2m + 3</tex> вершин, вершина <tex>a</tex> имеет не более <tex>n</tex> выделенных потомков, поэтому условие (3) выполнено.
}}
