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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
{{Лемма
 
{{Лемма
 
|statement=
 
|statement=
Пусть <tex>L</tex> — [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободный язык]] над алфавитом <tex>\Sigma</tex>. Существует такое <tex>n</tex>, что для любого слова <tex>\omega</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>, причем:
 
# либо <tex>uvx</tex>, либо <tex>xyz</tex> содержат все выделенные позиции;
 
# либо <tex>uvx</tex>, либо <tex>xyz</tex> содержат все выделенные позиции;
 
# <tex>vxy</tex> содержат не более <tex>n</tex> выделенных позиций;
 
# <tex>vxy</tex> содержат не более <tex>n</tex> выделенных позиций;
# существует <tex>A \in L</tex>, такой что <tex>S \Rightarrow^{*} uAz \Rightarrow^{*} uvAyz \Rightarrow^{*} uvxyz</tex>
+
# существует <tex>A \in L</tex>, такой что <tex>S \Rightarrow^{+} uAz \Rightarrow^{+} uvAyz \Rightarrow^{+} uvxyz</tex>
 
|proof=
 
|proof=
comming soon
+
Пусть <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> самый правый из них).
 
}}
 
}}

Версия 04:45, 2 декабря 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]uvx[/math], либо [math]xyz[/math] содержат все выделенные позиции;
  2. [math]vxy[/math] содержат не более [math]n[/math] выделенных позиций;
  3. существует [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]\triangleleft[/math]