Изменения

Перейти к: навигация, поиск

Лемма Огдена

1137 байт добавлено, 08:54, 2 декабря 2011
Нет описания правки
|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>, причем:
# x содержит выделенную позицию# либо <tex>uvxu</tex> и <tex>v</tex>, либо <tex>xyzy</tex> и <tex>z</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> в требуемом виде.
 
 
Условие (1) выполнено, поскольку <tex>x</tex> содержит выделенную вершину, а именно <tex>v_p</tex>. Очевидно, что условие(4) выполнено в силу предложенного разбиения <tex>\omega</tex>. Кроме того, <tex>u</tex> содержит выделенную вершину, а именно потомка некоторого сына вершины <tex>u_1</tex> (<tex>u_1</tex> лежит на пути от <tex>v_1</tex> до <tex>a</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) выполнено.
}}
100
правок

Навигация