Лемма Огдена

Лемма:

Для каждой контекстно-свободный грамматики [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], причем: либо [math]uvx[/math], либо [math]xyz[/math] содержат все выделенные позиции; [math]vxy[/math] содержат не более [math]n[/math] выделенных позиций; существует [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]