317
правок
Изменения
Нет описания правки
# либо <tex>u</tex> и <tex>v</tex>, либо <tex>y</tex> и <tex>z</tex> обе содержат выделенные позиции;
# <tex>vxy</tex> содержат не более <tex>n</tex> выделенных позиций;
# существует <tex>A \in N</tex>, такой что <tex>S \Rightarrow^{+} uAz \Rightarrow^{+} uvAyz \Rightarrow^{+} uvxyz</tex>.(т.е. <tex>\forall k \geqslant 0~uv^{k}xy^{k}z\in L</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> будем называть выделенными.
Условие (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) выполнено.
}}
== Пример не КС-языка, для которого выполняется лемма ==
Докажем, что можно построить такой язык, для которого будет выполняться лемма Огдена, однако он не будет контекстно-свободным. Выберем <tex>P</tex> {{---}} подмножество <tex>N</tex> и
<tex>A_{p} = \{ (ab)^n \mid P \in N \} </tex>
<tex>B_{p} = A_{p} \cup X^* \{aa, bb\}X^*</tex>
Языки над <tex>X=\{a, b\}</tex>.
Очевидно, что <tex>B_{p}</tex> КС, если <tex>A_{p}</tex> контекстно-свободен. <tex>B_{p}</tex> является рекурсивно-перечислимым, если и <tex>A_{p}</tex> им является.
Для <tex>B_{p}</tex> будет выполняться лемма Огдена для <tex>n = 4</tex>. Выбрав <tex>A_{p}</tex> таким образом, чтобы он был рекурсивно-перечислимым, мы создадим такой язык. (Такие языки существуют)
== См. также ==
*Hopcroft, Motwani and Ullman {{---}} Automata Theory, Languages, and Computation {{---}} Addison-Wesley, 1979. ISBN 81-7808-347-7.
*Ogden, W. (1968). "A helpful result for proving inherent ambiguity". Mathematical Systems Theory. 2 (3): 191–194.
*[http://archive.numdam.org/ARCHIVE/ITA/ITA_1978__12_3/ITA_1978__12_3_201_0/ITA_1978__12_3_201_0.pdf On languages satisfying Ogden's lemma]
[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]
