Лемма Огдена

Лемма

Лемма:

Для каждой контекстно-свободной грамматики [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]x[/math] содержит выделенную позицию; либо [math]u[/math] и [math]v[/math], либо [math]y[/math] и [math]z[/math] обе содержат выделенные позиции; [math]vxy[/math] содержат не более [math]n[/math] выделенных позиций; существует [math]A \in N[/math], такой что [math]S \Rightarrow^{+} uAz \Rightarrow^{+} uvAyz \Rightarrow^{+} uvxyz[/math]. (т.е. [math]\forall k \geqslant 0~uv^{k}xy^{k}z\in L[/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]

Пример не КС-языка, для которого выполняется лемма

Докажем, что можно построить такой язык, для которого будет выполняться лемма Огдена, однако он не будет контекстно-свободным. Выберем [math]P[/math] — подмножество [math]N[/math] и

[math]A_{p} = \{ (ab)^n \mid P \in N \} [/math]

[math]B_{p} = A_{p} \cup X^* \{aa, bb\}X^*[/math]

Языки над [math]X=\{a, b\}[/math].

Очевидно, что [math]B_{p}[/math] — КС, если [math]A_{p}[/math] контекстно-свободен. [math]B_{p}[/math] является рекурсивно-перечислимым, если и [math]A_{p}[/math] им является.

Для [math]B_{p}[/math] будет выполняться лемма Огдена для [math]n = 4[/math]. Выбрав [math]A_{p}[/math] таким образом, чтобы он был рекурсивно-перечислимым, мы создадим такой язык. (Такие языки существуют)

Пример не КС-языка, для которого выполняется лемма

Докажем, что язык [math]L = {a^mb^nc^l}[/math], где [math] m, n, l [/math] - попарно различны, не является КС-языком.

Предположим, что данный язык контекстно-свободный. Возьмем цепочку [math]\omega = a^kb^{k+(k-1)!} c^{k+k!}[/math], где [math]k[/math] - константа из леммы Огдена, выделив в ней все вхождения символа [math]a[/math]. Тогда при представлении цепочки [math]\omega[/math] в виде [math]uvxyz[/math] цепочка [math]x[/math] обязательно «зацепит» хотя бы один символ [math]a[/math]. Cледовательно, цепочка [math]v[/math] состоит только из символов [math]a[/math] (как и цепочка [math]u[/math]). А именно, [math]v = \alpha^p[/math], [math]1 \leqslant p \leqslant k+1[/math].

Тогда, если цепочка [math]x[/math] содержит и другие символы, кроме [math]a[/math], цепочка [math]y[/math] может входить либо в «зону» символов [math]b[/math] (целиком), либо в «зону» символов [math]c[/math] (целиком), так как расположение накачиваемых цепочек на стыках зон, очевидно, невозможно. В первом случае «кратность» [math]\alpha[/math] накачки цепочки [math]v[/math], которая уравняет числа символов [math]a[/math] и [math]c[/math], определяется из соотношения: [math]k + \alpha \cdot p = k + k![/math], то есть [math]\alpha = \frac{k!}{p} [/math]

Во втором случае [math]\frac{k-1!}{p}[/math] - кратная накачка цепочки [math]v[/math] уравняет числа вхождений символов [math]a[/math] и [math]b[/math]. Не исключено, наконец, что обе накачиваемые цепочки расположены в «зоне» символов [math]a[/math]. Но тогда одним из указанных выше способов накачки можно уравнять числа либо символов [math]a[/math] и [math]b[/math], либо [math]a[/math] и [math]c[/math].

Заметим, что возможность выделения символов существенно упрощает анализ данного языка, так как позволяет считать, что цепочка [math]v[/math] может расположиться единственным способом. Иначе, т.е. при использовании леммы о разрастании для кс-языков, решение задачи было бы, по меньшей мере, сильно затруднено.

См. также

Лемма о разрастании для КС-грамматик

Источники информации

• 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.
• On languages satisfying Ogden's lemma