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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показаны 43 промежуточные версии 14 участников)
Строка 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>x</tex> содержит выделенную позицию;
# <tex>vxy</tex> содержат более <tex>n</tex> выделенных позиций;
+
# либо <tex>u</tex> и <tex>v</tex>, либо <tex>y</tex> и <tex>z</tex> обе содержат выделенные позиции;
# существует <tex>A \in L</tex>, такой что <tex>S \Rightarrow^{*} uAz \Rightarrow^{*} uvAyz \Rightarrow^{*} uvxyz</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=
 
|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| \geqslant 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> самый правый из них). Рассмотрим <tex>v_1, v_2, \ldots, v_p</tex> {{---}} путь от корня до листа.
 +
 +
Будем называть ветвящейся ту вершину, у которой по крайне мере два сына имеют выделенных потомков. Докажем по индукции, что если среди <tex>v_1, v_2, \ldots, 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, \ldots, 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, \ldots, v_p</tex>, имеет выделенного потомка, лежащего слева от <tex>v_p</tex>. В противном случае назовем <tex>v_i</tex> правой ветвящейся вершиной. Рассмотрим последние <tex>2m + 3</tex> вершины, принадлежащие пути <tex>v_1, v_2, \ldots, v_p</tex>. Предположим, что хотя бы <tex>m + 2</tex> вершины {{---}} левые ветвящиеся (случай, когда хотя бы <tex>m + 2</tex> вершины {{---}} правые ветвящиеся, разбирается аналогично). Пусть <tex>u_1, u_2, \ldots, 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> в требуемом виде.
 +
 +
 +
Условие <tex>(1)</tex> выполнено, поскольку <tex>x</tex> содержит выделенную вершину, а именно <tex>v_p</tex>. Очевидно, что условие <tex>(4)</tex> выполнено в силу предложенного разбиения <tex>\omega</tex>. Кроме того, <tex>u</tex> содержит выделенную вершину, а именно потомка некоторого сына вершины <tex>u_1</tex>. Аналогично, выделенный потомок некоторого сына вершины <tex>a</tex> содержится в <tex>v</tex>. Таким образом, условие <tex>(2)</tex> выполнено. Поскольку между <tex>v_p</tex> и <tex>a</tex> не более <tex>2m + 3</tex> вершин, вершина <tex>a</tex> имеет не более <tex>n</tex> выделенных потомков, поэтому условие <tex>(3)</tex> выполнено.
 
}}
 
}}
 +
 +
== Примеры не КС-языка, для которого выполняется лемма ==
 +
Следует обратить особое внимание на то,  что лемма содержит лишь необходимые условия принадлежности КС языку.
 +
===Пример <tex> 1 </tex>===
 +
{{Утверждение
 +
|statement=Можно построить такой язык, для которого будет выполняться лемма Огдена, однако язык не будет контекстно-свободным.
 +
|proof=
 +
При анализе этого языка следует использовать алгебраические свойства множества. Выберем <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> таким образом, чтобы он был рекурсивно-перечислимым, мы создадим язык для которого будет выполняться лемма Огдена, однако язык не будет контекстно-свободным. (Такие языки существуют)<ref>A.V. Aho & J.D. Ullman, The Theory of Parsing, Translation and Compilimg, Vol. I, 1972</ref>
 +
}}
 +
 +
=== Пример <tex> 2 </tex> ===
 +
{{Утверждение
 +
|statement=Язык <tex>L = {a^mb^nc^l}</tex>,  где <tex> m, n, l </tex> {{---}} попарно различны, не является КС-языком.
 +
|proof=
 +
 +
Предположим, что данный язык контекстно-свободный. Возьмем цепочку <tex>\omega = a^kb^{k+(k-1)!} c^{k+k!}</tex>, где <tex>k</tex> {{---}} константа из леммы Огдена, выделив в ней все вхождения символа <tex>a</tex>. Тогда при представлении цепочки <tex>\omega</tex> в виде <tex>uvxyz</tex> цепочка <tex>x</tex> (по условию (1) леммы)  обязательно «зацепит» хотя бы один
 +
символ <tex>a</tex>. Cледовательно, цепочка <tex>v</tex> состоит только из символов <tex>a</tex> (как и цепочка <tex>u</tex>). А именно,
 +
<tex>v = \alpha^p</tex>, <tex>1 \leqslant p \leqslant k+1</tex>.
 +
 +
Тогда, если цепочка <tex>x</tex> содержит и другие символы, кроме <tex>a</tex>, цепочка <tex>y</tex> может входить либо в «зону» символов <tex>b</tex> (целиком), либо в «зону» символов <tex>c</tex> (целиком), так как расположение накачиваемых цепочек на стыках зон, очевидно, невозможно. В первом случае «кратность» <tex>\alpha</tex> накачки цепочки <tex>v</tex>, которая уравняет числа символов <tex>a</tex> и <tex>c</tex>, определяется из соотношения:
 +
<tex>k + \alpha \cdot p = k + k!</tex>, то есть <tex>\alpha = \dfrac{k!}{p} </tex>
 +
 +
Во втором случае <tex>\dfrac {k-1!}{p}</tex> - кратная накачка цепочки <tex>v</tex> уравняет числа вхождений символов <tex>a</tex> и <tex>b</tex>.
 +
Не исключено, наконец, что обе накачиваемые цепочки расположены в «зоне» символов <tex>a</tex>. Но тогда одним из указанных выше способов накачки можно уравнять числа либо символов <tex>a</tex> и <tex>b</tex>, либо <tex>a</tex> и <tex>c</tex>.
 +
 +
[[Файл:Ogden1.png|left|Рис. Цепочки контекстно-свободного языка]]
 +
 +
Заметим, что возможность выделения символов существенно упрощает анализ данного языка, так как позволяет считать, что цепочка <tex>v</tex> может расположиться единственным способом. Иначе, т.е. при использовании леммы о разрастании для кс-языков, решение задачи было бы, по меньшей мере, сильно затруднено.
 +
}}
 +
 +
== См. также ==
 +
*[[Лемма_о_разрастании_для_КС-грамматик|Лемма о разрастании для КС-грамматик]]
 +
 +
==Примечания==
 +
 +
<references />
 +
 +
== Источники информации ==
 +
 +
* [http://ru.wikipedia.org/wiki/Лемма_Огдена Wikipedia {{---}} Лемма Огдена]
 +
* ''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]
 +
* [http://ccf.ee.ntu.edu.tw/~yen/courses/toc14/chapter-2a.pdf Ogden's lemma]
 +
 +
[[Категория: Теория формальных языков]]
 +
[[Категория: Контекстно-свободные грамматики]]
 +
[[Категория: Опровержение контекстно-свободности языка]]

Текущая версия на 19:07, 4 сентября 2022

Для бесконечного языка применение приведённых в предыдущем разделе приёмов приведёт к началу построения в общем случае бесконечного числа правил грамматики. Требуется более мощный аппарат, которым служит доказываемая ниже лемма Огдена.

Лемма

Лемма:
Для каждой контекстно-свободной грамматики [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 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| \geqslant 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, \ldots, v_p[/math] — путь от корня до листа.

Будем называть ветвящейся ту вершину, у которой по крайне мере два сына имеют выделенных потомков. Докажем по индукции, что если среди [math]v_1, v_2, \ldots, 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, \ldots, 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, \ldots, v_p[/math], имеет выделенного потомка, лежащего слева от [math]v_p[/math]. В противном случае назовем [math]v_i[/math] правой ветвящейся вершиной. Рассмотрим последние [math]2m + 3[/math] вершины, принадлежащие пути [math]v_1, v_2, \ldots, v_p[/math]. Предположим, что хотя бы [math]m + 2[/math] вершины — левые ветвящиеся (случай, когда хотя бы [math]m + 2[/math] вершины — правые ветвящиеся, разбирается аналогично). Пусть [math]u_1, u_2, \ldots, 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] в требуемом виде.


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

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

Следует обратить особое внимание на то, что лемма содержит лишь необходимые условия принадлежности КС языку.

Пример [math] 1 [/math]

Утверждение:
Можно построить такой язык, для которого будет выполняться лемма Огдена, однако язык не будет контекстно-свободным.
[math]\triangleright[/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] таким образом, чтобы он был рекурсивно-перечислимым, мы создадим язык для которого будет выполняться лемма Огдена, однако язык не будет контекстно-свободным. (Такие языки существуют)[1]
[math]\triangleleft[/math]

Пример [math] 2 [/math]

Утверждение:
Язык [math]L = {a^mb^nc^l}[/math], где [math] m, n, l [/math] — попарно различны, не является КС-языком.
[math]\triangleright[/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] (по условию (1) леммы) обязательно «зацепит» хотя бы один символ [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 = \dfrac{k!}{p} [/math]

Во втором случае [math]\dfrac {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] может расположиться единственным способом. Иначе, т.е. при использовании леммы о разрастании для кс-языков, решение задачи было бы, по меньшей мере, сильно затруднено.
[math]\triangleleft[/math]

См. также

Примечания

  1. A.V. Aho & J.D. Ullman, The Theory of Parsing, Translation and Compilimg, Vol. I, 1972

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