Лемма Огдена — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
{{Лемма
 
{{Лемма
 
|statement=
 
|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>\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>x</tex> содержит выделенную позицию
 
# либо <tex>u</tex> и <tex>v</tex>, либо <tex>y</tex> и <tex>z</tex> обе содержат выделенные позиции;
 
# либо <tex>u</tex> и <tex>v</tex>, либо <tex>y</tex> и <tex>z</tex> обе содержат выделенные позиции;
 
# <tex>vxy</tex> содержат не более <tex>n</tex> выделенных позиций;
 
# <tex>vxy</tex> содержат не более <tex>n</tex> выделенных позиций;
Строка 11: Строка 11:
 
Пусть <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</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>n_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, 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>.
 
Поскольку <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> в требуемом виде.
+
[[Файл: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) выполнено.
+
Условие (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) выполнено.
 
}}
 
}}

Версия 06:46, 9 декабря 2011

Лемма:
Для каждой контекстно-свободный грамматики [math]\Gamma =\langle \Sigma, N, S \in N, P \subset N^{+}\times (\Sigma\cup N)^{*}\rangle[/math] существует такое [math]n[/math], что для любого слова [math]\omega \in L(\Gamma)[/math], длины не менее [math]n[/math], и для любых выделенных в [math]\omega[/math] не менее [math]n[/math] позиций [math]\omega[/math] может быть представлено в виде [math]\omega=uvxyz[/math], причем:
  1. [math]x[/math] содержит выделенную позицию
  2. либо [math]u[/math] и [math]v[/math], либо [math]y[/math] и [math]z[/math] обе содержат выделенные позиции;
  3. [math]vxy[/math] содержат не более [math]n[/math] выделенных позиций;
  4. существует [math]A \in L[/math], такой что [math]S \Rightarrow^{+} uAz \Rightarrow^{+} uvAyz \Rightarrow^{+} uvxyz[/math]
Доказательство:
[math]\triangleright[/math]

Введем следующие обозначения: [math]m = |N|[/math] и [math]l[/math] — длина самой длинной правой части правила из [math]P[/math]. Тогда в качестве [math]n[/math] возьмем [math]l^{2m + 3}[/math]. Рассмотрим дерево разбора [math]T[/math] для произвольного слова [math]\omega \in L(\Gamma)[/math], у которого [math]|\omega| \ge n[/math]. В силу выбора [math]n[/math] в [math]T[/math] будет по крайне мере один путь от корня до листа длины, не менее [math]2m + 3[/math]. Произвольным образом выделим в [math]\omega[/math] не менее [math]n[/math] позиций. Соответствующие этим позициям листья дерева [math]T[/math] будем называть выделенными.

Пусть [math]v_1[/math] — корень [math]T[/math], а [math]v_{i + 1}[/math] — сын [math]v_i[/math], который имеет среди своих потомков наибольшее число выделенных листьев (если таких несколько, то [math]v_{i + 1}[/math] самый правый из них). Рассмотрим [math]v_1, v_2, ..., v_p[/math] — путь от корня до листа.

Будем называть ветвящейся ту вершину, у которой по крайне мере два сына имеют выделенных потомков. Докажем по индукции, что если среди [math]v_1, v_2, ..., v_i[/math] вершин есть [math]k[/math] ветвящихся, то [math]v_{i + 1}[/math] имеет хотя бы [math]l^{2m + 3 - k}[/math] выделенных потомков.
База индукции: [math]i = 0[/math]. Тогда [math]k = 0[/math] и [math]v_1[/math] имеет по крайне мере [math]n[/math] выделенных потомков, поскольку является корнем.
Индукционный переход. Если [math]v_i[/math] не является ветвящейся вершиной, то [math]v_{i + 1}[/math] имеет такое же число ветвящихся потомков как и [math]v_i[/math]. Если [math]v_i[/math] — ветвящаяся вершина, то [math]v_{i + 1}[/math] имеет не более чем в [math]l[/math] раз меньшее число выделенных потомков.

Поскольку [math]v_1[/math] имеет хотя бы [math]n = l^{2m + 3}[/math] выделенных потомков, то [math]v_1, v_2, ..., v_p[/math] содержит по крайне мере [math]2m + 3[/math] ветвящиеся вершин. Заметим, что [math]v_p[/math] — лист, поэтому [math]p \gt 2m + 3[/math].

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


Условие (1) выполнено, поскольку [math]x[/math] содержит выделенную вершину, а именно [math]v_p[/math]. Очевидно, что условие (4) выполнено в силу предложенного разбиения [math]\omega[/math]. Кроме того, [math]u[/math] содержит выделенную вершину, а именно потомка некоторого сына вершины [math]u_1[/math]. Аналогично выделенный потомок некоторого сына вершины [math]a[/math] содержится в [math]v[/math]. Таким образом, условие (2) выполнено. Поскольку между [math]v_p[/math] и [math]a[/math] не более [math]2m + 3[/math] вершин, то вершина [math]a[/math] имеет не более [math]n[/math] выделенных потомков, поэтому условие (3) выполнено.
[math]\triangleleft[/math]