200
правок
Изменения
→Источники информации
Для бесконечного языка применение приведённых в предыдущем разделе приёмов приведёт к началу построения в общем случае бесконечного числа правил грамматики. Требуется более мощный аппарат, которым служит доказываемая ниже лемма Огдена.
== Лемма ==
{{Лемма
|statement=
# <tex>vxy</tex> содержат не более <tex>n</tex> выделенных позиций;
# существует <tex>A \in LN</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> 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]
[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]
[[Категория: Опровержение контекстно-свободности языка]]