editor
143
правки
Изменения
Нет описания правки
{{Лемма
|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>x</tex> содержит выделенную позицию;
# либо <tex>u</tex> и <tex>v</tex>, либо <tex>y</tex> и <tex>z</tex> обе содержат выделенные позиции;
# <tex>vxy</tex> содержат не более <tex>n</tex> выделенных позиций;
# существует <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> будем называть выделенными.
