Викиконспекты - Вклад участника [ru]

Комплексное евклидово пространство

2017-01-19T12:32:10Z

94.25.229.56: /* Неравенство Шварца(Коши-Буняковского) */

{{Определение
|definition=
Пусть <tex>E</tex> - линейное пространство над <tex>\mathbb{C}</tex>

В <tex>E</tex> задана эрмитова метрическая форма, т.е <tex>G:\: E\times E\longrightarrow \mathbb{C}</tex> co свойствами:

<tex>1)\: G(\alpha x_{1}+\beta x_{2};y)=\alpha G(x_{1},y)+\beta G(x_{2},y)</tex>, где <tex>\alpha</tex> , <tex>\beta</tex> - комплексные числа

<tex>2)\: G(x,y)=\overline{G(y,x)}</tex>; <tex>G(x,x)=\overline{G(x,x)} \Longrightarrow G(x,x) \in \mathbb{R}</tex>

<tex>3)\: G(x,x) \ge 0;\: G(x,x)=0 \Longleftrightarrow x = 0_{E}</tex>
}}
NB 1: <tex>G</tex> полуторалинейна:
<tex>G(x;\alpha y_{1}+\beta y_{2})=\overline{\alpha}G(x,y_{1})+\overline{\beta}G(x,y_{2})</tex>

NB 2: <tex>G(x,y)=\left\langle x,y\right\rangle _{G}; x,y \in E(</tex>над <tex> \mathbb{C})</tex>

NB 3: <tex>G(x,y)=\left\langle x,y\right\rangle _{G}</tex>

<tex>\Vert x\Vert_{G}=\sqrt{\left\langle x,x\right\rangle _{G}};
\:\Vert\alpha x\Vert_{G}=\sqrt{\left\langle \alpha x,\alpha x\right\rangle _{G}}=\sqrt{\alpha\cdot\overline{\alpha}\cdot\left\langle x,x\right\rangle _{G}}=|\alpha|\cdot\Vert x\Vert_{G}
</tex>
==Примеры==
<tex>E = \mathbb{C}^{n}</tex>

<tex>\left\langle x,y\right\rangle =\sum\limits_{i=1}^{n}\xi^{i}\overline{\eta^{i}}</tex>

<tex>\left\langle y,x\right\rangle =\sum\limits_{i=1}^{n}\eta^{i}\overline{\xi^{i}}=\overline{\sum\limits \overline{\eta^{i}}\xi^{i}}=\overline{\left\langle x,y\right\rangle }</tex>;

<tex>\left\langle x,x\right\rangle =\sum\limits_{i=1}^{n}\xi^{i}\overline{\xi^{i}}=\sum\limits_{i=1}^{n}|\xi^{i}|^{2}>0</tex>

==Неравенство Шварца(Коши-Буняковского)==
{{Теорема
|statement= <tex>\forall\: x,y\in \mathbb{C}:\;|\left\langle x,y\right\rangle _{G}|\leq\Vert x\Vert_{G}\cdot\Vert y\Vert_{G}</tex>
|proof=
Рассмотрим <tex>\left\langle \lambda x+y;\lambda x+y\right\rangle =\Vert\lambda x+y\Vert^{2}\geq0</tex>, где <tex>\lambda \in \mathbb{R}</tex>

<tex>\left\langle \lambda x+y;\lambda x+y\right\rangle = \left\langle \lambda x;\lambda x\right\rangle +\left\langle \lambda x;y\right\rangle +\left\langle y;\lambda x\right\rangle +\left\langle y;y\right\rangle </tex>
<tex>= \lambda\cdot\overline{\lambda}\left\langle x,x\right\rangle +\lambda\cdot(\left\langle x;y\right\rangle +\overline{\left\langle x;y\right\rangle })+\left\langle y,y\right\rangle </tex>
<tex>= \Vert x\Vert^{2}\cdot\lambda^{2}+\lambda\cdot 2Re\left\langle x;y\right\rangle + \Vert y\Vert^{2}\geq0</tex> - многочлен второй степени, все коэффициенты вещественные

<tex>D \le 0</tex>

<tex> D/4=(-Re\left\langle x,y\right\rangle )^{2}-\Vert x\Vert^{2}\cdot\Vert y\Vert^{2}\le0\Longrightarrow |Re\left\langle x,y\right\rangle |\le\Vert x\Vert\cdot\Vert y\Vert</tex> - верно для <tex>\forall x,y\in E</tex>. Назовём это неравенство <tex>(\times)</tex> - крестик.

Трюк: пусть <tex>\left\langle x,y\right\rangle = |\left\langle x,y\right\rangle|\cdot e^{i\varphi}</tex>, где <tex>\varphi=arg\left\langle x,y\right\rangle</tex>. Тогда пусть в <tex>(\times): y \longrightarrow y\cdot e^{i\varphi} \Longrightarrow \Vert e^{i\varphi}y\Vert=|e^{i\varphi}|\cdot\Vert y\Vert</tex>

Заметим, что <tex>\left\langle x,e^{i\varphi}y\right\rangle= \overline{e^{i\varphi}}\left\langle x,y \right\rangle =
\overline{e^{i\varphi}}e^{i\varphi}\left|\left\langle x, y\right\rangle\right| = \left|\left\langle x, y\right\rangle\right|</tex>

Заменим в <tex>(\times)</tex> <tex>y</tex> на <tex>e^{i\varphi}y \: : |Re\left\langle x,e^{i\varphi}y\right\rangle|
\le\Vert x\Vert\cdot\Vert e^{i\varphi}y\Vert</tex>

левая часть равна <tex>|Re|\left\langle x,y\right\rangle|| = |\left\langle x,y\right\rangle|</tex>

правая часть равна <tex>\Vert x \Vert\cdot\Vert y\Vert</tex>

Таким образом, <tex>|\left\langle x,y\right\rangle| \le \Vert x \Vert\cdot\Vert y\Vert</tex>
}}
{{Теорема
|about=следствие из Шварца, неравенство треугольника
|statement= <tex>\Vert x+y \Vert \leq \Vert x\Vert\cdot\Vert y\Vert</tex>
|proof= Рассмотрим <tex>\left\langle x+y, x+y\right\rangle={\Vert x+y \Vert}^{2} = \Vert x\Vert^{2}+\left\langle x,y\right\rangle+\left\langle y,x\right\rangle + \Vert y\Vert^{2} = \Vert x\Vert^{2}+2Re\left\langle x,y\right\rangle+ \Vert y\Vert^{2}</tex>

<tex>Re\left\langle x,y\right\rangle \le |\left\langle x,y\right\rangle| \le \Vert x\Vert\cdot\Vert y\Vert</tex> (из неравенства Шварца)

Таким образом, <tex>{\Vert x+y \Vert}^{2} \le \Vert x\Vert^{2}+2\cdot\Vert x\Vert\cdot\Vert y\Vert+ \Vert y\Vert^{2}=(\Vert x\Vert+\Vert y\Vert)^2</tex>

Взяв корень из левой и правой части, получим искомое неравенство.
}}
[[Категория: Алгебра и геометрия 1 курс]]

Функциональный анализ

2016-10-17T22:14:44Z

94.25.229.56: /* 46. О размерности Ker(I-A) компактного А. */

Здесь я постараюсь написать теоретический минимум по второй части курса функционального анализа.

Большая часть материала взята из Википедии, чтобы не перебивать формулы и все такое. Все остальное бралось из конспектов, лучший из них лежит на firun.ru

'''Функциональный анализ''' — раздел математики, в котором изучаются бесконечномерные пространства (в основном пространства функций) и их отображения.

==Краткое содержание 5 семестра (версия 2009)==

*'''Метрическое пространство''' <tex>M</tex> есть множество точек с '''метрикой''' <tex>d \colon M \times M \to \mathbb{R}</tex>:
# <tex>d(x,\;y) \ge 0 ; d(x,\;y)=0\Leftrightarrow x=y</tex>.
# <tex>d(x,\;y)=d(y,\;x)</tex>.
# <tex>d(x,\;z)\leqslant d(x,\;y)+d(y,\;z)</tex>.

*Метрическое пространство называется '''полным''', если любая фундаментальная последовательность в нём сходится к некоторому элементу этого пространства.

*'''Банаховым пространством''' (''B-пространством'') называется нормированное линейное пространство, полное по метрике, порождённой нормой.

*'''Пространство непрерывных функций''' — линейное нормированное пространство, элементами которого являются непрерывные на отрезке <tex>[a,b]</tex> функции (обычно обозначается <tex>{\mathrm C}[a,b]</tex>). '''Норма''' в этом пространстве определяется следующим образом: <tex>||x||_{{\mathbf C}[a,b]}=\max_{t\in [a,b]}|x(t)|</tex>

* '''Теорема Рисса — Фреше:''' Для любого непрерывного линейного функционала <tex>f</tex> на Гильбертовом пространстве <tex> H</tex> существует единственный вектор <tex>y \in H</tex> такой, что <tex>f(x)= \langle x,y \rangle</tex> для любого <tex>x \in H</tex>. При этом норма линейного функционала <tex>f</tex> совпадает с нормой вектора <tex>y</tex>: <tex>\|f\|=\sup_{\|x\|=1} |f(x)|= \sqrt{\langle y,y \rangle}</tex>. Теорема также означает, что пространство всех линейных ограниченных функционалов над <tex>H</tex> изоморофно пространству <tex>H</tex>.

*'''Теорема (Хан-Банах)''' о продолжении линейного функционала с сохранением мажоранты: любой линейный функционал <tex>f(x)</tex>, определённый на подпространстве <tex>L</tex> линейного пространства <tex>X</tex> и удовлетворяющий условию <tex>|f(x)| \leq p(x), \forall x \in L</tex>, где <tex>p(x)</tex> — некоторый положительно однородный функционал (определённый на всем пространстве <tex>X</tex>) то <tex>f(x)</tex> может быть продолжен на все пространство <tex>X</tex> с сохранением этого условия.

*'''Теорема (Хан-Банах)''' о непрерывном продолжении линейного функционала: всякий линейный функционал <tex>f(x)</tex>, определённый на линейном многообразии <tex>L</tex> линейного нормированного пространства <tex>X</tex>, можно продолжить на все пространство с сохранением нормы.

*Следствие: для любых двух различных точек линейного пространства существует линейный функционал, определённый на всем пространстве и такой, что его значения в этих точках различны.

* '''Ядром''' линейного отображения <tex>f\colon A\to B</tex> называются подмножество <tex>A</tex>, которое отображается в нуль: <tex>\mbox{Ker}\,f = \{ x\in A\mid f(x) = 0 \}</tex>. Ядро линейного отображения образует подпространство в линейном пространстве <tex>A</tex>.

*Пусть <tex>A</tex> — оператор, действующий в банаховом пространстве <tex>E</tex>. Число λ называется '''регулярным''' для оператора <tex>A</tex>, если оператор <tex>R(\lambda)=(A - \lambda I)^{-1}</tex>, называемый '''резольвентой''' оператора <tex>A</tex>, определён на всём <tex>E</tex> и непрерывен. Множество регулярных значений оператора <tex>A</tex> называется '''резольвентным множеством''' этого оператора, а дополнение резольвентного множества — '''спектром''' этого оператора.

==Билеты - 5 семестр==
===1. Принцип вложенных шаров в полном МП.===

{{Теорема
|statement=
<tex>X</tex> - полное МП, <tex>\overline{V}_{r_i} \subset X,\; \overline{V}_{r_{i+1}} \subset \overline{V}_{r_i},\; r_i \rightarrow 0 \Rightarrow \exists ! d \in \cap \overline{V}_{r_i}</tex>
}}

===2. Теорема Бэра о категориях.===

{{Определение
|definition=
'''Замыкание''' <tex>Cl \; A = F</tex>, если <tex>F</tex> - замкнутое, <tex>A \subseteq F</tex> и <tex>\forall</tex> замкнутого <tex>G: A \subseteq G \Rightarrow F \subseteq G</tex>
}}
{{Определение
|definition=
<tex>A</tex> '''всюду плотно''' в <tex>X</tex>, если <tex>Cl \; A = X</tex>
}}
{{Определение
|definition=
<tex>A</tex> '''нигде не плотно''' в <tex>X</tex>, если <tex>\forall V_r(x)\; \exists V_{r_1}(y) \subset V_r(x): V_{r_1}(y) \cap A = \O</tex>
}}
{{Определение
|definition=
<tex>A</tex> '''I категории по Бэру''' в <tex>X</tex>, если <tex>A = \cup A_i</tex> (счетное объединение), <tex>A_i</tex> нигде не плотно в <tex>X</tex>, иначе '''II категории'''
}}
{{Теорема
|statement=
<tex>X</tex> - полное МП <tex>\Rightarrow X</tex> - II категории в <tex>X</tex>
}}

===3. Критерий компактности Хаусдорфа в МП.===

[[Теорема Хаусдорфа об ε-сетях]]

===4. Пространство <tex>R^{\infty}</tex>: метрика, покоординатная сходимость.===

<tex>(x_1^n, x_2^n, \ldots, x_m^n, \ldots) \to (x_1, x_2, \ldots, x_m, \ldots) \Leftrightarrow \forall m : x_m^n \to x_m</tex>

<tex>\rho(x,y) = \sum\limits_{m=1}^{\infty}\frac{1}{2^m} \cdot \frac{|x_m - y_m|}{1+|x_m - y_m|}</tex>

===5. Компактность прямоугольника в <tex>R^{\infty}</tex>.===

ну компактен, хуле

===6. Постранство S(E, <tex>\mu</tex>).===

{{Определение
|definition=
<tex>S(E, \mu)</tex> - пространство измеримых функций на <tex>E</tex> по <tex>\mu</tex>. На этом пространстве определена метрика <tex>\rho (f, g) = \int\limits_E \frac{|f-g|}{1+|f-g|} d\mu</tex>
}}

===7. Норма в линейном множестве, определение предела по норме, арифметика предела.===

{{Определение
|definition=
'''Норма''' <tex>\| \cdot \| : X \to \mathbb{R}</tex>
#<tex>\|x\| \geq 0, \; \|x\| = 0 \Leftrightarrow x=0</tex>
#<tex>\|\alpha x\| = |\alpha|\|x\|</tex>
#<tex>\|x+y\| \leq \|x\| + \|y\|</tex>
}}
{{Определение
|definition=
<tex>x_n</tex> '''сходится по норме''' к <tex>x</tex>, если <tex>\|x_n - x\| \to 0</tex>
}}

===8. Эквивалентность норм в конечномерном НП.===

{{Определение
|definition=
<tex>\| \cdot \|_1 \sim \| \cdot \|_2</tex>, если <tex>\exists a, b \; \forall x : a\|x\|_1 \leq \|x\|_2 \leq b\|x\|_1</tex>
}}
{{Теорема
|author=Рисс
|statement=
В конечномерном пространстве любые две нормы эквивалентны
}}

===9. Замкнутость конечномерного линейного подмножества НП.===

{{Теорема
|author=следствие из теоремы Рисса
|statement=
<tex>X</tex> - НП, <tex>Y</tex> - конечномерное линейное подмножество <tex>X \Rightarrow Y</tex> - замкнутое
}}

===10. Лемма Рисса о почти перпендикуляре, пример ее применения.===

{{Лемма
|author=Рисс, о почти перпендикуляре
|statement=
<tex>Y</tex> - собственное подпространство <tex>X \Rightarrow \forall \varepsilon \in (0, 1) \; \exists z_{\varepsilon} \in X : \|z_{\varepsilon}\| = 1,\; \rho(z_{\varepsilon}, Y) \geq 1 - \varepsilon</tex> (где <tex>\rho(z, Y) = \inf\limits_{y \in Y} \|z-y\|</tex>)
|proof=
<tex>\forall z \notin Y \; \forall \varepsilon\; \exists y_{\varepsilon} \in Y : \rho(z, Y) \leq \|z - y_{\varepsilon}\| \leq \frac{1}{1 - \varepsilon} \cdot \rho(z, Y)</tex> (по свойствам inf). Тогда положим <tex>z_{\varepsilon}</tex> из условия леммы равным <tex>\frac{z - y_{\varepsilon}}{\|z - y_{\varepsilon}\|}</tex>
}}
{{Лемма
|author=пример применения леммы
|statement=
<tex>X</tex> - бесконечномерное НП <tex>\Rightarrow</tex> любой шар в нем - не компакт
}}

===11. Банаховы пространства на примерах С[0,1] и Lp(E).===

{{Определение
|definition=
'''Банахово пространство''' - полное нормированное пространство
}}
{{Определение
|definition=
<tex>C[0,1]</tex> - пространство непрерывных функций на <tex>[0,1]</tex>. На этом пространстве определена норма <tex>\|f\| = \max\limits_{t \in [0,1]}|f(t)|</tex>
}}
{{Определение
|definition=
<tex>L_p(E)</tex> - пространство измеримых на <tex>E</tex> функций<tex>f : \int\limits_E|f|^p < +\infty</tex>. На этом пространстве определена норма <tex>\|f\| = \sqrt[p]{\int\limits_E |f|^p}</tex>
}}

===12. Определение скалярного произведения, равенство параллелограмма, неравенство Шварца.===

{{Определение
|definition=
'''Скалярное произведение''' <tex>\langle x,y \rangle</tex>
#<tex>\langle\alpha x_1 + \beta x_2,y \rangle = \alpha\langle x_1, y \rangle + \beta \langle x_2, y \rangle </tex>
#<tex>\langle x,y \rangle = \langle y,x \rangle </tex>
#<tex>\langle x,x \rangle \geq 0, \langle x,x \rangle = 0 \Leftrightarrow x = 0</tex>
}}
'''Равенство параллелограмма''': <tex>2\|x\|^2 + 2\|y\|^2 = \|x+y\|^2 + \|x-y\|^2</tex>

'''Неравенство Шварца''': <tex>|\langle x,y \rangle| \leq \sqrt{\langle x,x \rangle} \cdot \sqrt{\langle y,y \rangle}</tex>

===13. Наилучшее приближение в НП в случае конечномерного подпространства.===

{{Теорема
|statement=
<tex>\forall x \; \exists y^* : E_n(x) = \|x - y^*\|</tex>
}}

===14. Наилучшее приближение в унитарном пространстве, неравенство Бесселя.===

<tex>\{e_1, e_2, \ldots, e_n, \ldots\}</tex> - ортонормированная система.

<tex>\alpha_i(x) = \langle x,e_i \rangle, \; \sum \alpha_i(x)e_i</tex> - абстрактный ряд Фурье

<tex>\delta_n(x) = \sum\limits_{i=1}^n \alpha_i(x)e_i,\; E_n(x) = \|x-\delta_n(x)\|</tex>

'''Неравенство Бесселя''': <tex>\sum \alpha_i^2(x) \leq \|x\|^2</tex>

===15. Определение Гильбертова пространства, сепарабельность и полнота.===

{{Определение
|definition=
'''Гильбертово пространство''' - полное унитарное пространство. То есть для него выполняется:
#Введено скалярное произведение
#Введена норма: <tex>\|x\| = \sqrt{\langle x,x \rangle}</tex>
#<tex>\|x_n - x_m\| \to 0 \Rightarrow \exists x : \|x_n - x\| \to 0</tex>
}}
{{Определение
|definition=
Пространство '''сепарабельно''', если у него существует счетное абсолютно плотное подмножество
}}
{{Лемма
|statement=
В гильбертовом пространстве существует ортонормированный базис тогда и только тогда, когда оно сепарабельно
}}

===16. Теорема Рисса-Фишера, равенство Парсеваля.===

{{Теорема
|author=Рисс - Фишер
|statement=
Пусть <tex>\{e_1, e_2, \ldots, e_n, \ldots\}</tex> - ортонормированная система в гильбертовом пространстве <tex>H</tex>, <tex>\sum\limits_{i=1}^{\infty} \alpha_i^2 \leq +\infty</tex>. Тогда <tex>\exists ! x \in H : \alpha_i = \langle x, e_i \rangle</tex> и выполняется '''равенство Парсеваля''': <tex>\sum \alpha_i^2(x) = \|x\|^2</tex>
}}

===17.Наилучшее приближение в Н для случая выпуклого,замкнутого множества,<tex>H=H_1 \oplus H_2</tex>===

{{Теорема
|statement=
<tex>M</tex> - замкнутое выпуклое подмножество гильбертова пространства <tex>H</tex>. Тогда <tex>\forall x \in H\; \exists \overline{x} : \|x - \overline{x}\| = \inf\limits_{y \in M} \|x - y\|</tex>
}}
{{Теорема
|statement=
<tex>H_1</tex> - подпространство <tex>H,\; H_2 = H_1^{\perp} = \{y \mid \forall x \in H_1 : y \perp x\}</tex>. Тогда <tex>\forall x \in H\; \exists!x_1, x_2 : x = x_1 + x_2,\; x_i \in H_i</tex>
}}

===18. Непрерывный линейный функционал и его норма.===

{{Определение
|definition=
Линейный функционал <tex>f</tex> '''ограничен''', если <tex>\|f\| = \sup\limits_{\|x\| \leq 1} |f(x)| < +\infty</tex>
}}
{{Определение
|definition=
Линейный функционал <tex>f</tex> '''непрерывен''' в <tex>x</tex>, если
<tex>\forall \{x_n\} : x_n \to x \Rightarrow f(x_n) \to f(x)</tex>
}}
{{Лемма
|statement=
<tex>f</tex> непрерывен в <tex>x</tex> <tex>\Leftrightarrow</tex> <tex>f</tex> непрерывен в <tex>0</tex>
}}
{{Теорема
|statement=
<tex>f</tex> непрерывен <tex>\Leftrightarrow</tex> <tex>f</tex> ограничен
}}

===19. Связь между непрерывностью линейного функционала и замкнутостью его ядра.===

{{Определение
|definition=
'''Ядро''' линейного функционала <tex>Ker f = \{x \mid f(x) = 0\}</tex>
}}
{{Теорема
|statement=
<tex>f</tex> непрерывен <tex>\Leftrightarrow</tex> <tex>Ker f</tex> замкнуто
}}

===20. Продолжение по непрерывности линейного функционала со всюду плотного линейного подмножества НП.===

{{Лемма
|statement=
Пусть <tex>X</tex> - НП, <tex>Y</tex> всюду плотно в <tex>X</tex>, <tex>f</tex> - ограниченный линейный функционал из <tex>Y</tex>. Тогда <tex>\exists !g : X \to \mathbb{R} : g(y) = f(y),\; \|g\| = \|f\|</tex> (существует единственное продолжение, сохраняющее норму)
}}

===21. Теорема Хана-Банаха для НП (сепарабельный случай).===

{{Лемма
|statement=
Пусть <tex>X</tex> - линейное множество с введенной на нем полунормой <tex>p(x)</tex>, <tex>Y \subset X</tex>, <tex>f : Y \to \mathbb{R}</tex>, <tex>|f(y)| \leq p(y)</tex> (то есть функционал подчинен полунорме), <tex>z \notin Y</tex>, <tex>Z = L(Y, z)</tex>. Тогда <tex>\exists g : Z \to \mathbb{R} : g(y) = f(y),\; g(x) \leq p(x)</tex>
}}
{{Теорема
|author=Хан - Банах
|statement=
Пусть <tex>X</tex> - линейное множество с введенной на нем полунормой <tex>p(x)</tex>, <tex>Y \subset X</tex>, <tex>f : Y \to \mathbb{R}</tex>, <tex>|f(y)| \leq p(y)</tex>. Тогда <tex>\exists g : X \to \mathbb{R} : g(y) = f(y),\; g(x) \leq p(x)</tex>, то есть продолжение <tex>f</tex>
}}

===22. Два следствия из теоремы Хана-Банаха.===

'''Следствие 1''': <tex>X</tex> - НП, <tex>x_0 \in X</tex> <tex>\Rightarrow</tex> <tex>\exists f : f(x_0) = \|x_0\|,\; \|f\| = 1</tex>

'''Следствие 2''': <tex>X</tex> - НП, <tex>\{e_1, e_2, \ldots, e_n\}</tex> - ЛНЗ <tex>\Rightarrow</tex> <tex>\exists \{f_1, f_2, \ldots, f_n\} : f_i(e_j) = \delta_{ij}</tex> (биортогональная система)

===23. Теорема Рисса об общем виде линейного непрерывного функционала в Н.===

{{Теорема
|author=Рисс
|statement=
<tex>\forall f \in H^*\; \exists ! y \in H : f(x) = \langle x, y \rangle</tex>, причем <tex>\|f\| = \|y\|</tex>
}}

===24. Непрерывный линейный оператор и его норма.===

{{Определение
|definition=
Линейный оператор <tex>A</tex> '''ограничен''', если <tex>\|A\| = \sup\limits_{\|x\| \leq 1} \|Ax\| < +\infty</tex>
}}
{{Определение
|definition=
Линейный оператор <tex>A</tex> '''непрерывен''' в <tex>x</tex>, если
<tex>\forall \{x_n\} : x_n \to x \Rightarrow Ax_n \to Ax</tex>
}}
{{Теорема
|statement=
<tex>A</tex> непрерывен <tex>\Leftrightarrow</tex> <tex>A</tex> ограничен
}}

===25. Продолжение линейного оператора по непрерывности.===

{{Лемма
|statement=
<tex>A: X_1 \to Y,\; Cl\;X_1 = X,\; Y</tex> - Банахово, <tex>\|A\| < +\infty</tex>. Тогда <tex>\exists !\tilde{A} : X \to Y : \tilde{A}x = Ax,\; \|\tilde{A}\| = \|A\|</tex>
}}

===26. Полнота пространства L(X,Y).===

{{Определение
|definition=
<tex>L(X,Y)</tex> - пространство непрерывных линейных операторов из <tex>X</tex> в <tex>Y</tex>
}}
{{Лемма
|statement=
<tex>Y</tex> - Банахово <tex>\Rightarrow L(X,Y)</tex> - Банахово
}}

===27. Теорема Банаха-Штейнгауза.===

{{Теорема
|author=Банах - Штейнгауз
|statement=
Пусть <tex>\forall x : \sup\limits_n\|A_nx\| < +\infty</tex> (то есть последовательность поточечно ограничена). Тогда <tex>\sup\limits_n\|A_n\| < +\infty</tex> (то есть последовательность равномерно ограничена)
}}

===28. Условие непрерывной обратимости лин. оператора.===

{{Теорема
|author=
|statement=
Пусть <tex>A</tex> - ограниченный линейный оператор из <tex>X</tex> в <tex>Y</tex>, и <tex>\exists m\; \forall x \in X : m \|x\| \leq \|Ax\|</tex>. Тогда <tex>R(A)</tex> замкнуто, <tex>\exists A^{-1}:Y \to X,\; \|A^{-1}\| < +\infty</tex>
}}

===29. Теорема Банаха о непрерывной обратимости I-С.===

{{Теорема
|author=Банах
|statement=
Пусть <tex>X</tex> - Банахово, <tex>C \in L(X),\; \|C\| < 1</tex>. Тогда <tex>I - C</tex> непрерывно обратим.
}}

===30. Теорема Банаха об обратном операторе.===

{{Теорема
|author=Банах
|statement=
Пусть <tex>A</tex> - биективный линейный ограниченный оператор из <tex>X</tex> в <tex>Y</tex> (оба Банаховы). Тогда <tex>\exists A^{-1}:Y \to X,\; \|A^{-1}\| < +\infty</tex>
}}

===31. Теорема о замкнутом графике.===

{{Теорема
|statement=
<tex>A</tex> непрерывен <tex>\Leftrightarrow</tex> <tex>G_A</tex> замкнут
}}

===32. Теорема об открытом отображении.===

{{Теорема
|statement=
<tex>A</tex> непрерывен, <tex>G</tex> - открыто <tex>\Rightarrow</tex> <tex>A(G)</tex> - открыто
}}

===33. Теорема об открытости резольвентного множества.===

{{Определение
|definition=
'''Резольвентное множество''' линейного оператора <tex>\rho(A) = \{\lambda \mid \exists (A - \lambda I)^{-1}</tex> - непрерывный<tex>\}</tex>
}}
{{Определение
|definition=
'''Спектр''' линейного оператора <tex>\sigma(A) = \mathbb{R} \setminus \rho(A)</tex>
}}
{{Теорема
|statement=
<tex>\rho(A)</tex> открыто
}}

===34. Вхождение спектра в круг радиуса ||А||.===

{{Лемма
|statement=
<tex>\sigma(A) \subset \{\lambda \mid |\lambda| \leq \|A\| \}</tex>
}}

===35. Спектральный радиус.===

{{Определение
|definition=
'''Спектральный радиус''' <tex>r_{\sigma}(A) = \inf\limits_n \sqrt[n]{\|A^n\|}</tex>
}}
{{Теорема
|statement=
Относительно спектрального радиуса любого линейного оператора верны следующие утверждения:
#<tex>r_{\sigma}(A) = \lim\limits_{n \to \infty} \sqrt[n]{\|A\|^n}</tex>
#<tex>\sigma(A) \subset \{\lambda \mid |\lambda| \leq r_{\sigma}(A) \}</tex>
}}

===36. Аналитичность резольвенты.===

эммм...

===37. Непустота спектра ограниченного оператора.===

эммм...

===38. А* и его ограниченность.===

{{Определение
|definition=
'''Сопряженным''' к оператору <tex>A : X \to Y</tex> называется такой оператор <tex>A^* : Y^* \to X^*</tex>, что <tex>A^* \varphi = \varphi \circ A</tex>, то есть <tex>A^*\varphi = f : f(x) = \varphi(Ax)</tex>
}}
{{Лемма
|statement=
<tex>\|A\|=\|A^*\|</tex>
}}

===39. Ортогональные дополнения Е и Е*.===

{{Определение
|definition=
'''Ортогональным дополнением''' линейного множества <tex>M \subset E</tex> называется множество <tex>M^{\perp} = \{f \in E^* \mid \forall x \in M f(x) = 0\}</tex>.
<tex>M^{*\perp} = \{x \in E \mid \forall f \in M^* f(x) = 0\}</tex>. Заметим, что из непрерывности функционалов следует замкнутость ортогональных дополнений.
}}
{{Лемма
|statement=
<tex>E^{\perp} = \{0\},\; E^{*\perp} = \{0\}</tex>
}}

===40. Ортогональное дополнение R(A).===

{{Теорема
|statement=
Пусть <tex>A</tex> - ограниченный ЛО, <tex>R(A)</tex> замкнуто. Тогда <tex>R(A) = (Ker A^*)^{\perp}</tex>
}}

===41. Ортогональное дополнение R(A*).===

{{Теорема
|statement=
Пусть <tex>A</tex> - ограниченный ЛО, <tex>R(A)</tex> замкнуто. Тогда <tex>R(A^*) = (Ker A)^{\perp}</tex>
}}

===42. Арифметика компактных операторов.===

{{Определение
|definition=
Оператор <tex>A</tex> '''компактен''', если <tex>\forall G : G</tex> - ограниченное <tex>\Rightarrow A(G)</tex> - относительно компактно
}}
{{Лемма
|statement=
Компактные операторы обладают следующими свойствами:
#<tex>A</tex> - компактный, <tex>B</tex> - ограниченный <tex>\Rightarrow</tex> <tex>AB</tex> и <tex>BA</tex> - компактные
#<tex>A_n</tex> - компактные, <tex>A_n \to A</tex> <tex>\Rightarrow</tex> <tex>A</tex> - компактный
#<tex>A : X \to Y</tex> - компактный, <tex>X</tex> - бесконечномерно <tex>\Rightarrow</tex> оператор <tex>A</tex> не может быть непрерывно обратим
}}

===43. О компактности А*, сепарабельность R(A).===

{{Теорема
|statement=
<tex>A</tex> - компактный <tex>\Rightarrow</tex> <tex>A^*</tex> - компактный
}}

===44. Базис Шаудера, лемма о координатном пространстве.===

{{Определение
|definition=
Система точек <tex>\{e_1, e_2, \ldots, e_n, \ldots \} \subset X</tex> называется '''базисом Шаудера''', если любой элемент пространства <tex>X</tex> единственным образом представим в виде линейной комбинации этих точек
}}

===45. Почти конечномерность компактного оператора.===

{{Теорема
|statement=
<tex>X</tex> - пространство с базисом Шаудера, <tex>A : X \to X</tex> - компактный <tex>\Rightarrow</tex> <tex>\forall \varepsilon \; \exists B, C : A = B+C,\; \|C\| < \varepsilon,\; B</tex> - конечномерный (то есть <tex>R(B)</tex> конечномерно), <tex>B</tex> и <tex>C</tex> компактны
}}

===46. О размерности Ker(I-A) компактного А.===

{{Лемма
|statement=
<tex>A</tex> - компактный <tex>\Rightarrow \dim(Ker (I - A)) < +\infty</tex>
}}

===47. Условие замкнутости R(A) на языке решений операторного уравнения.===

{{Лемма
|statement=
Пусть <tex> A \in L(E, F) </tex>, и <tex> \exists \alpha \; \forall y \in R(A)\; \exists x \in E : \|x\| \leq \alpha \|y\| , Ax=y</tex>. Тогда <tex> R(A) </tex> - замкнуто.
}}

===48. О замкнутости R(I-A) компактного А.===

{{Лемма
|statement=
Пусть оператор <tex> A </tex> - компактный. Тогда <tex> R(I - A) </tex> - замкнуто
}}

===49. Лемма о Ker(I-A)*n компактного А.===

{{Лемма
|statement=
Пусть оператор <tex>A</tex> - компактный. Тогда <tex> \exists k : Ker(I - A)^{k + 1} = Ker(I - A)^k</tex>
}}

===50. Об условии справедливости равенства R(I-A)=Е.===

{{Лемма
|statement=
Пусть оператор <tex>A</tex> - компактный. Тогда <tex> R(I - A) = X \Leftrightarrow Ker(I - A) = \{0\}</tex>
}}

===51. Альтернатива Фредгольма-Шаудера.===

{{Теорема
|author=альтернатива Фредгольма - Шаудера
|statement=
Пусть <tex>A : X \to X</tex> - компактный. Рассмотрим уравнение <tex>y = x - Ax</tex>. Возможны 2 случая:
#<tex>Ker(I-A) = \{0\}</tex>. Тогда уравнение имеет решение при любом <tex>y</tex>
#<tex>Ker(I-A) \neq \{0\}</tex>. Тогда уравнение имеет решение при <tex>y \in (Ker (I-A)^*)^{\perp}</tex>
}}

===52. О спектре компактного оператора.===

{{Теорема
|statement=
Пусть оператор <tex>A</tex> - компактный. Тогда его спектр не более, чем счетный, и предельной точкой в нем может быть только <tex>0</tex>
}}

==Билеты - 6 семестр==
===1. Сопряженный оператор и его ограниченность===

Будем работать с <tex>E</tex>, как с банаховым пространством.

'''Def''': Пространство всех линейных функционалов на <tex>E</tex> образует линейное пространство (прошлый семестр).
Это пространство называется '''сопряжённым''' к <tex>E</tex>, оно обычно обозначается <tex>E^*</tex>.

'''Def''': Пусть <tex>A:E\to F</tex> — непрерывный линейный оператор, действующий из банахова пространства <tex>E</tex> в банахово пространство <tex>F</tex>. И пусть <tex>E^*, F^*</tex> — сопряжённые пространства. Обозначим <tex>\forall x\in E, f\in F^* \langle Ax,f\rangle =f(Ax)</tex>. Если <tex>f</tex> — фиксировано, то <tex>\langle Ax,f \rangle </tex> — линейный непрерывный функционал в <tex>E, \langle Ax,f \rangle \in E^*</tex>. Таким образом, для <tex>\forall f\in F^*</tex> определён линейный непрерывный функционал из <tex>E^* </tex>, поэтому определён оператор <tex>A^*:F^*\to E^*</tex>, такой что <tex>\langle Ax,f \rangle=\langle x,A^*f \rangle</tex>.
<tex>A^*</tex> называется '''сопряжённым оператором'''.

'''Th''': Пусть задан линейный оператор <tex>A:E\to F</tex>. Тогда норма оператора <tex>A^*:F^*\to E^*</tex> совпадает с нормой <tex>A</tex>.

(оператор проектирования ??)

===2. Ортогональные дополнения Е и Е*===

'''Def''': Пусть <tex>S</tex> некоторое линейное множество. Тогда его '''ортогональное дополнение''' <tex>S^\perp = \{f \in E^* | f(x) = 0 \; \forall x \in S\}</tex>.

'''Th''': Имеют место соотношения: <tex>E^\perp = \{0\}</tex>; <tex>(E^*)^\perp = \{0\}</tex>.

(при доказательстве используем теорему Хана-Банаха)

===3. Ортогональное дополнение R(A)===

(Здесь можно написать красивый текст из конспекта про важность теорем и все такое)

'''Th''': Пусть задан линейный оператор <tex>A:E\to F</tex>, где <tex>E</tex> и <tex>F</tex> банаховы. Тогда <tex>\overline{R(A)} = (Ker(A^*))^\perp</tex>.

===4. Ортогональное дополнение R(A*)===

'''Th''': Пусть множество значений оператора <tex>A</tex> замкнуто: <tex>R(A) = Cl(R(A))</tex>. Тогда верно <tex>R(A^*) = Cl(R(A^*)) = (Ker(A))^\perp</tex>.

----

===5. Арифметика компактных операторов===

'''Def''': Линейный оператор <tex>A:E\to F</tex> называется '''компактным''', если он переводит любое ограниченное множество из <tex>E</tex> в относительно компактное множество в <tex>F</tex>.

Примером является оператор Фредгольма: <tex>\psi(s) = \int\limits_a^b\!K(s, t) \varphi(t)\, dt</tex>.

Установим несколько свойств:

'''Th''': Пусть операторы <tex>A, B:E\to E</tex> такие, что <tex>A</tex> компактен, а <tex>B</tex> ограничен. Тогда операторы <tex>AB</tex> и <tex>BA</tex> компактны.

===6. О компактности А*, сепарабельность R(A)===
[[Теорема о компактности сопряженного оператора]]

===7. Базис Шаудера, лемма о координатном пространстве===

'''Def''': Система векторов <tex>\{e_n\}</tex> топологического векторного пространства <tex>E</tex> называется '''базисом Шаудера''', если каждый элемент <tex>f \in E</tex> разлагается в ''единственный'', сходящийся к <tex>f</tex> ряд по <tex>\{e_n\}</tex>: <tex>f= \sum_{i=1}^{\infty} f_i e_i</tex>, где <tex>f_i</tex> — числа, называемые коэффициентами разложения вектора <tex>f</tex> по базису <tex>\{e_n\}</tex>.

===8. Почти конечномерность компактного оператора===

----
Теперь походим вокруг альтернативы Фредгольма-Шаудера.

===9. О размерности Ker(I-A) компактного А===
'''Утв.''' Пусть <tex> A </tex> - компактный оператор, <tex> H = I - A </tex>.
Тогда, <tex> dim (Ker H)< +\infty </tex>

'''Следствие''' Множество решений операторного уравнения <tex> Ax = \lambda x, \lambda \in \mathbb{R} </tex> конечномерно.

===10. Условие замкнутости R(A) на языке решений операторного уравнения===
'''Утв.''' Пусть <tex> A \in L(E, F) </tex> и <tex> \exists \alpha = const : \forall y \in R(A), y = A(x), \exists x \in E : \|x\| \le \alpha \|y\| </tex>. ''Тогда'', <tex> R(A) </tex> - замкнуто.

===11. О замкнутости R(I-A) компактного А===
'''Утв.''' Пусть оператор <tex> A </tex> - компактный. Тогда, <tex> R(I - A) </tex> - замкнуто.

===12. Лемма о Ker(I-A)*n компактного А===
'''Утв.''' Пусть оператор <tex>A</tex> - компактный.
Тогда <tex> \exists k \in \mathbb{N}</tex>: <tex>Ker(I - A)^{k + 1} = Ker(I - A)^k</tex>

===13. Об условии справедливости равенства R(I-A)=Е===
'''Утв.''' Пусть <tex> A </tex> - компактный оператор. Тогда,
<tex> R(I - A) = E \Leftrightarrow Ker(I - A) = \{0\}</tex>

===14. Альтернатива Фредгольма-Шаудера===
'''Th.''' (''Альтернатива Фредгольма-Шаудера'')

Пусть <tex> A : E \rightarrow E </tex> - компактный оператор, <tex>E - B</tex>-пространство.

Тогда, <tex> \forall \lambda \neq 0</tex> возможны только 2 случая:
# <tex> Ker(\lambda I - A) = \{0\} \Rightarrow \lambda \in \rho(A) </tex>
# <tex> Ker(\lambda I - A) \neq \{0\} \Rightarrow </tex> (уравнение <tex>(\lambda I - A)x = y</tex> разрешимо относительно <tex>x) \Leftrightarrow y \in (Ker(\lambda I^{*} - A^{*}))^{\bot}</tex>

===15. О спектре компактного оператора===

----
Теперь это называется Теорией Гильберта-Шмидта

===16. О вещественности спектра ограниченного самосопряженного оператора===
'''Утв.''' Пусть <tex> A </tex> - ограниченный и самосопряженный оператор. Тогда, <tex>\sigma(A) \subset \mathbb{R}</tex>

===17. О характеризации спектра и резольвентного множества ограниченного самосопряженного оператора===
'''Th.''' Пусть <tex> A </tex> - ограниченный и самосопряженный оператор. Тогда,

# <tex> \lambda \in \rho(A) \Leftrightarrow \exists m > 0 : \|(\lambda I - A)x\| \ge m \|x\| </tex>
# <tex> \lambda \in \sigma(A) \Leftrightarrow \exists \{x_n | \|x_n\| = 1\}</tex>, т.ч. <tex> \lim_{n \rightarrow \infty}\|(\lambda I - A)x_n\| = 0 </tex>

===18. О числах m- и m+===
'''Def.''' <tex> m_{-} = \inf_{\|x\| = 1}\langle Ax, x \rangle</tex>

'''Def.''' <tex> m_{+} = \sup_{\|x\| = 1}\langle Ax, x \rangle</tex>

'''Def.''' Если для некоторого оператора <tex>L : \langle Ax, x \rangle \ge 0 </tex>, то <tex>L</tex> называется '''неотрицательным'''.

'''Th.''' Пусть <tex>A</tex> - ограниченный и самосопряженный оператор. Тогда, <tex>\sigma(A) \subset [m_{-}, m_{+}]</tex>, и
<tex>m_{-} \in \sigma(A), m_{+} \in \sigma(A)</tex>

===19. Спектральный радиус ограниченного самосопряженного оператора===
'''Th.''' Пусть <tex>A</tex> - ограниченный, самосопряженный оператор. Тогда, <tex>\|A\| = r_{\sigma} = \max\{|m_{-}|, |m_{+}|\}</tex>

===20. Теорема Гильберта-Шмидта===

===21. О диагонализации компактного самосопряженного оператора и разложении его резольвенты===

----
Элементы нелинейного функционального анализа.

===22. Теорема Банаха о сжимающем отображении===

'''Def''': Пусть на замкнутом шаре <tex>\overline{V} \subset X</tex>, где <tex>X</tex> - метрическое пространство, определён оператор <tex>A: \overline{V} \subset X \to X</tex>. Он называется сжатием на <tex>\overline{V}</tex>, если <tex>\exists\alpha\in(0; 1)</tex> такой, что для <tex>{\forall}x,y \in M</tex> выполняется <tex>{\rho(Ax,Ay)\leqslant\alpha{\cdot}\rho(x,y)}</tex>.

'''Th.'''(''Банаха о неподвижной точке'')
Пусть <tex>T : \overline{V} \to \overline{V}</tex> и является сжатием, тогда в этом шаре у оператора <tex>T</tex> <tex>\exists !</tex> неподвижная точка.

[[Теорема Банаха о неподвижной точке]]

===23. Дифференциал Фреше===

Рассмотрим <tex>T : V_r(x_0) \to Y</tex>, где <tex>V_r(x_0) \subset X</tex> и, кроме того, <tex>X, Y</tex> - нормированные пространства.

Пусть <tex>\|\delta x \| < r</tex>. Тогда, очевидно, <tex>x + \delta x \in V_r(x_0)</tex>.

Обозначим <tex>\delta T(x_0, \delta x) = T(x_0 + \delta x) - T(x_0)</tex>.

'''Def.''' Отображение <tex>T</tex> называется дифференцируемым по Фреше в точке <tex>x_0</tex>, если существует оператор <tex>A_{x_0} \in L(X,Y)</tex> такой, что <tex>\delta T(x_0, \delta x) = A_{x_0}(\delta x) + o(\delta x)</tex>, где <tex>o(\delta x)</tex> несёт следующий смысл: <tex>\frac{ {\|o(\delta x)\|}_Y } {{\| \delta x \|}_X} \to 0</tex>.

Обычно, в случае дифференцируемого отображения используют следующее обозначение: <tex>T_{x_0}' = A_{x_0}</tex>. Подчеркнем, что <tex>T_{x_0}': X \to Y</tex>. Аргументом является "отклонение" некоторой точки <tex>x'</tex> от <tex>x_0</tex>: <tex>x - x_0</tex>. А результат применения оператора: <tex>T(x') - T(x_0)</tex> с точностью до <tex>o(\delta x = x' - x)</tex>.

'''Lm.''' Рассмотрим оператор <tex>T(x, t) =\int_0^1 K(t,s,x(s))ds</tex>, действующий на <tex>x(t) \in C[0,1]</tex>, и где <tex>K = W(v, y, z); v, y \in [0, 1]</tex>, <math> z \in \mathbb R</math>, и существует непрерывная по <tex>v, y, z</tex> производная <tex>\frac{\partial K}{\partial z}</tex>. Тогда в любой точке пространства <tex>C[0,1]</tex> это отображение дифференцируемо и его производная Фреше задается интегральным линейным по <tex>\delta x</tex>оператором: <tex>T_{x_0}'(\delta x, t) = \int_0^1 \frac{\partial K}{\partial z}(t, s, x_0(s))\delta x(s) ds</tex>.

===24. Неравенство Лагранжа===

'''Lm.''' (''Неравенство Лагранжа'')
Пусть <tex>X, Y</tex> -- нормированные пространства, <tex>V</tex> -- некоторый шар в <tex>X</tex> и дан оператор <tex>T : V \to Y</tex> и на всем этом шаре <tex>\exists T'(x)</tex>. Тогда для любых <tex>a, b \in V : \|T(b) - T(a)\| \le M {\|b - a\|}_X</tex>, где <tex>M = sup_{x \in [a, b]}\|T'(x)\|</tex>.

===25. Локальная теорема о неявном отображении===

'''Th.'''(''о неявном отображении'')

Пусть <tex>V</tex> - шар в <tex> X, V \subset X</tex>, а <tex>W \subset Y</tex> - шар в <tex>Y</tex>, и задан оператор <tex>T : {V} \times {W} \rightarrow Y</tex>.

Пусть <tex>x_0 \in V,\: y_0 \in W,\: T(x_0, y_0) = 0 \in Y</tex>.

Пусть <tex> \forall x \in V, \forall y \in W \quad \exists T^{'}_y </tex> - дифференциал Фреше, непрерывный как отображение переменных <tex>x</tex> и <tex>y</tex>.

Пусть также <tex>T^{'}_{y}(x_0, y_0)</tex> - непрерывно обратим.

'''Тогда''' задача о неявном отображении для <tex>T(x, y) = 0</tex> c начальным решением <tex>T(x_0, y_0) = 0</tex> разрешима в некоторых окрестностях точек <tex>x_0, y_0</tex>, а именно: для любого <tex>x' \in V_{\delta_1}(x_0)</tex> существует единственное <tex>y' \in V_{\delta_2}(y_0) : T(x', y') = 0</tex> .

===26. Теорема о локальной обратимости отображения===

'''Следствие локальной теоремы о неявном отображении'''

Дано отображение <tex>T : V_r(x_0) \subset X \to V_r(y_0) \subset Y</tex>. <tex>T(x_0) = y_0</tex>. Если существует непрерывно-обратимое отображение <tex>T_x '(x_0)</tex> и отображение <tex>T_x '(x)</tex>существует на всем шаре, то для любого <tex>y \in V_{\delta_2}(y_0)</tex> существует единственный <tex>x \in V_{\delta_1}(x_0) : T(x) = y</tex>.

===27. Локальная теорема о простой итерации===

'''Th.'''(''о простой итерации'')
<tex>T: V \subset X \to X</tex> и существует <tex>\overline{x} \in V : \overline{x} = T(\overline{x})</tex>. Кроме того, пусть <tex>\|T'(\overline{x})\| < 1</tex>. Тогда <tex>\exists \delta : \forall x_0 \in V_\delta(\overline{x})</tex> и <tex>x_{n + 1} = T(x_n)</tex> выполнено <tex>lim(x_n) = \overline{x}</tex>.

===28. Локальная теорема о методе Ньютона-Канторовича===

'''Th.'''(''о методе Ньютона-Канторовича'')
<tex>F : V \to X, \exists \overline{x} \in V : F(\overline{x}) = 0</tex>.
Кроме этого, пусть на <tex> V</tex> <tex> \exists F'(x)</tex>, непрерывная на нем. Тогда существует окрестность точки <tex>\overline{x}</tex>, в которой метод Ньютона-Канторовича осуществим. Т.е. <tex>\exists \delta > 0 : x_0 \in V_\delta(\overline{x}), x_{n + 1} = x_n - (F_{x_n}')^{-1}(F(x_n))</tex> и тогда: <tex> lim(x_n) = \overline{x} </tex>.

===29. О проекторах Шаудера===
'''Lm.'''(''о проекторах Шаудера'')
Пусть <tex>T: D \subset X \to X</tex>, где <tex>X</tex> -- нормированное пространство. Тогда существует последовательность компактных операторов <tex>T_n: T_n \rightrightarrows T</tex> на D, и при этом <tex>\forall T_n</tex> лежит в конечномерном подпространстве <tex>X</tex>.

===30. Теорема Шаудера о неподвижной точке===
'''Th.'''(''Шаудера'')
Если <tex>D</tex> -- ограниченное выпуклое замкнутое множество в Банаховом пространстве <tex>X</tex> и оператор <tex>T : D \to D</tex>, то у этого оператора на <tex>D</tex> существует неподвижная точка.

Устранение левой рекурсии

2013-01-18T20:28:07Z

94.25.229.56: /* Алгоритм устранения произвольной левой рекурсии */

{{Определение
|definition=Говорят, что [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная (КС) грамматика]] <tex>\Gamma</tex> содержит '''непосредственную левую рекурсию''' (direct left recursion), если она содержит правило вида <tex>A \to A\alpha</tex>.
}}
{{Определение
|definition=Говорят, что КС-грамматика <tex>\Gamma</tex> содержит '''левую рекурсию (left recursion)''', если в ней существует вывод вида <tex>A \Rightarrow^* A\alpha</tex>.
}}

Методы нисходящего разбора (top-down parsers) не в состоянии работать с леворекурсивными грамматиками. Проблема в том, что продукция вида <tex>A \Rightarrow^* A\alpha</tex> может применяться бесконечно долго, так и не выработав некий терминальный символ, который можно было бы сравнить со строкой. Поэтому требуется преобразование грамматики, которое бы устранило левую рекурсию.

==Устранение непосредственной левой рекурсии==
Опишем процедуру, устраняющую все правила вида <tex>A \to A\alpha</tex>, для фиксированного нетерминала <tex>A</tex>.

<ol>
<li>Запишем все правила вывода из <tex>A</tex> в виде:
<tex>A \to A\alpha_1\,|\,\ldots\,|\,A\alpha_n\,|\,\beta_1\,|\,\ldots\,|\,\beta_m </tex>, где
<ul>
<li> <tex>\alpha</tex> {{---}} непустая последовательность терминалов и нетерминалов (<tex>\alpha \nrightarrow \varepsilon </tex>);</li>
<li> <tex>\beta</tex> {{---}} непустая последовательность терминалов и нетерминалов, не начинающаяся с <tex>A</tex>.</li>
</ul>
<li>Заменим правила вывода из <tex>A</tex> на <tex>A \to\beta_1A^\prime\, |\, \ldots\, |\, \beta_mA^\prime \,|\, \beta_1 \,|\, \ldots \,|\, \beta_m</tex>.</li>

<li>Создадим новый нетерминал <tex>{A^\prime} \to \alpha_1{A^\prime}, |\, \ldots\, |\, \alpha_n{A^\prime} | \alpha_1\, |\, \ldots\, |\, \alpha_n</tex>. </li>
</li>
</ol>

Изначально нетерминал <tex>A</tex> порождает сроки вида <tex>\beta\alpha_{i0}\alpha_{i1} \ldots \alpha_{ik}</tex>. В новой грамматике нетерминал <tex>A</tex> порождает <tex>\beta{A^\prime}</tex>, а <tex>A^\prime</tex> порождает строки вида <tex>\alpha_{i0}\alpha_{i1} \ldots \alpha_{ik}</tex>. Из этого очевидно, что изначальная грамматика эквивалентна новой.

===Пример===
<tex>A \to S\alpha | A\alpha</tex>

<tex>S \to A\beta</tex>

Есть непосредственная левая рекурсия <tex>A \to A\alpha</tex>. Добавим нетерминал <tex>A^\prime</tex> и добавим правила <tex>A \to S\alpha{A^{\prime}}</tex>, <tex> A^{\prime} \to \alpha{A^{\prime}} </tex>.

Новая грамматика:

<tex>A \to S\alpha{A^{\prime}} | S\alpha</tex>

<tex>A^{\prime} \to \alpha{A^{\prime}}</tex>

<tex>S \to A\beta</tex>

В новой грамматике нет непосредственной левой рекурсии, но нетерминал <tex>A</tex> леворекурсивен, так как есть <tex> A \Rightarrow S\alpha{A^{\prime}} \Rightarrow A\beta\alpha{A^{\prime}} </tex>

==Алгоритм устранения произвольной левой рекурсии==
Воспользуемся [[Удаление_eps-правил_из_грамматики | алгоритмом удаления <tex> \varepsilon </tex>-правил]]. Получим грамматику без <tex> \varepsilon </tex>-правил для языка <tex>L(\Gamma) \setminus \lbrace \epsilon \rbrace</tex>.

Упорядочим нетерминалы и будим добиваться того, чтобы не было правил вида <tex>A_i \to A_j\alpha</tex>, где <tex>j \le i</tex>.
Если данное условие выполняется для всех<tex>A_i</tex>, то в грамматике нет <tex>A_i \to^* A_i</tex>, а значит не будет левой рекурсии.

Пусть <tex>N = \lbrace A_1, A_2, \ldots , A_n \rbrace</tex> {{---}} упорядоченное множество всех нетерминалов.
<div>
for все нетерминалы <tex>A_i</tex>
for все нетерминалы <tex>A_j</tex>, такие, что <tex> 1 \leq j < i </tex> и
рассмотреть все правила вывода из <tex>A_j</tex>: <tex>A_j \to \delta_1 | \ldots | \delta_k</tex>.
заменить каждое правило <tex>A_i \to A_j \gamma</tex> на <tex>A_i \to \delta_1\gamma | \ldots | \delta_k\gamma</tex>.
устранить непосредственную левую рекурсию для <tex>A_i</tex>.
</div>

Если <tex>\varepsilon</tex> присутствовал в языке исходной грамматики, добавим новый начальный символ <tex>S'</tex> и правила <tex>S' \to S \, | \, \varepsilon </tex>.

После <tex>i</tex> итерации внешнего цикла в любой продукции внешнего цикла в любой продукции вида <tex>A_k \to A_l\alpha, k < i</tex>, должно быть <tex>l > k</tex>. В результате при следующей итерации внутреннего цикла растет нижний предел <tex>m</tex> всех продукций вида <tex>A_i \to A_m\alpha</tex> до тех пор, пока не будет достигнуто <tex>i \le m </tex>.

После <tex>i</tex> итерации внешнего цикла в грамматике будут только правила вида <tex>A_i \to A_j\alpha</tex>, где <tex>j > i</tex>.
Можно заметить, что неравенство становится строгим только после применения алгоритма устранения непосредственной левой рекурсии. При этом добавляются новые нетерминалы. Пусть <tex>{A^\prime}_i </tex> новый нетерминал. Можно заметить, что нет правила вида <tex>\ldots \to {A^\prime}_i</tex>, где <tex>{A^\prime}_i</tex> самый левый нетерминал, а значит новые нетерминалы можно не рассматривать во внешнем цикле.

На <tex>i</tex> итерации внешнего цикла все правила вида <tex>A_i \to A_j \gamma</tex> где <tex> j < i </tex> заменяются на <tex>A_i \to \delta_1\gamma | \ldots | \delta_k\gamma</tex> где <tex>A_j \to \delta_1 | \ldots | \delta_k</tex>. Очевидно, что одна итерация алгоритма не меняет язык, а значит язык получившийся в итоге грамматики совпадает с исходным.

===Асимптотика===
Пусть <tex>a_i</tex> количество правил для нетерминала <tex>A_i</tex>.
Тогда <tex>i</tex> итерация внешнего цикла будет выполняться за <tex>O(\sum\limits_{A_i \to A_j, j < i} a_j) + O(a_i)</tex>, что меньше чем <tex>O(\sum\limits_{i=1}^n a_j)</tex>, значит асимптотика алгоритма <tex>O(n\sum\limits_{i=1}^n a_j)</tex>.

Проблема этого алгоритма в том, что в зависимости от порядка нетерминалов в множестве размер грамматки может получиться экспоненциальным.

Пример грамматики для которой имеет значение порядок нетерминалов

<tex>A_1 \to 0 | 1</tex>

<tex>A_{i+1} \to {A_i}0 | {A_i}1 </tex> для <tex>1 \leq i < n</tex>

Упорядочим множество нетерминалов по возрастанию индексов. Легко заметить, что правила для <tex>A_i</tex> будут представлять из себя все двоичные вектора длины <tex>i</tex>, а значит размер грамматики будет экспоненциальным. Если упорядочить нетерминалы по убыванию в грамматике изменений не будет.

==Пример==
Дана грамматика

<tex>A \to S\alpha </tex>

<tex>S \to S\beta | A\gamma | b</tex>

Среди правил <tex>A</tex> непосредственной рекурсии нет, поэтому во время первой итерации внешнего цикла ничего не происходит.
Во время второй итерации внешнего цикла правило <tex> S \to A\gamma </tex> переходит в <tex> S \to S\alpha\gamma </tex>.

Грамматика имеет вид

<tex>A \to S\alpha </tex>

<tex>S \to{S}{\beta} | {S}{\alpha}{\gamma} | \beta</tex>

Устраняем левую рекурсию для <tex>S</tex>

<tex> S \to\beta{S_1}</tex>

<tex> {S_1} \to\beta{S_1} | \alpha\gamma{S_1}</tex>

==Литература==
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' — '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)
* ''Robert C. Moore'' — [http://aclweb.org/anthology-new/A/A00/A00-2033.pdf Removing Left Recursion from Context-Free Grammars ]

[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]

Устранение левой рекурсии

2013-01-18T20:13:39Z

94.25.229.56: /* Алгоритм устранения произвольной левой рекурсии */

{{Определение
|definition=Говорят, что [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная (КС) грамматика]] <tex>\Gamma</tex> содержит '''непосредственную левую рекурсию''' (direct left recursion), если она содержит правило вида <tex>A \to A\alpha</tex>.
}}
{{Определение
|definition=Говорят, что КС-грамматика <tex>\Gamma</tex> содержит '''левую рекурсию (left recursion)''', если в ней существует вывод вида <tex>A \Rightarrow^* A\alpha</tex>.
}}

Методы нисходящего разбора (top-down parsers) не в состоянии работать с леворекурсивными грамматиками. Проблема в том, что продукция вида <tex>A \Rightarrow^* A\alpha</tex> может применяться бесконечно долго, так и не выработав некий терминальный символ, который можно было бы сравнить со строкой. Поэтому требуется преобразование грамматики, которое бы устранило левую рекурсию.

==Устранение непосредственной левой рекурсии==
Опишем процедуру, устраняющую все правила вида <tex>A \to A\alpha</tex>, для фиксированного нетерминала <tex>A</tex>.

<ol>
<li>Запишем все правила вывода из <tex>A</tex> в виде:
<tex>A \to A\alpha_1\,|\,\ldots\,|\,A\alpha_n\,|\,\beta_1\,|\,\ldots\,|\,\beta_m </tex>, где
<ul>
<li> <tex>\alpha</tex> {{---}} непустая последовательность терминалов и нетерминалов (<tex>\alpha \nrightarrow \varepsilon </tex>);</li>
<li> <tex>\beta</tex> {{---}} непустая последовательность терминалов и нетерминалов, не начинающаяся с <tex>A</tex>.</li>
</ul>
<li>Заменим правила вывода из <tex>A</tex> на <tex>A \to\beta_1A^\prime\, |\, \ldots\, |\, \beta_mA^\prime \,|\, \beta_1 \,|\, \ldots \,|\, \beta_m</tex>.</li>

<li>Создадим новый нетерминал <tex>{A^\prime} \to \alpha_1{A^\prime}, |\, \ldots\, |\, \alpha_n{A^\prime} | \alpha_1\, |\, \ldots\, |\, \alpha_n</tex>. </li>
</li>
</ol>

Изначально нетерминал <tex>A</tex> порождает сроки вида <tex>\beta\alpha_{i0}\alpha_{i1} \ldots \alpha_{ik}</tex>. В новой грамматике нетерминал <tex>A</tex> порождает <tex>\beta{A^\prime}</tex>, а <tex>A^\prime</tex> порождает строки вида <tex>\alpha_{i0}\alpha_{i1} \ldots \alpha_{ik}</tex>. Из этого очевидно, что изначальная грамматика эквивалентна новой.

===Пример===
<tex>A \to S\alpha | A\alpha</tex>

<tex>S \to A\beta</tex>

Есть непосредственная левая рекурсия <tex>A \to A\alpha</tex>. Добавим нетерминал <tex>A^\prime</tex> и добавим правила <tex>A \to S\alpha{A^{\prime}}</tex>, <tex> A^{\prime} \to \alpha{A^{\prime}} </tex>.

Новая грамматика:

<tex>A \to S\alpha{A^{\prime}} | S\alpha</tex>

<tex>A^{\prime} \to \alpha{A^{\prime}}</tex>

<tex>S \to A\beta</tex>

В новой грамматике нет непосредственной левой рекурсии, но нетерминал <tex>A</tex> леворекурсивен, так как есть <tex> A \Rightarrow S\alpha{A^{\prime}} \Rightarrow A\beta\alpha{A^{\prime}} </tex>

==Алгоритм устранения произвольной левой рекурсии==
Воспользуемся [[Удаление_eps-правил_из_грамматики | алгоритмом удаления <tex> \varepsilon </tex>-правил]]. Получим грамматику без <tex> \varepsilon </tex>-правил для языка <tex>L(\Gamma) \setminus \lbrace \epsilon \rbrace</tex>.

Упорядочим нетерминалы и будим добиваться того, чтобы не было правил вида <tex>A_i \to A_j\alpha</tex>, где <tex>j \le i</tex>.
Если данное условие выполняется для всех<tex>A_i</tex>, то в грамматике нет <tex>A_i \to^* A_i</tex>, а значит не будет левой рекурсии.

Пусть <tex>N = \lbrace A_1, A_2, \ldots , A_n \rbrace</tex> {{---}} упорядоченное множество всех нетерминалов.
<div>
for все нетерминалы <tex>A_i</tex>
for все нетерминалы <tex>A_j</tex>, такие, что <tex> 1 \leq j < i </tex> и
рассмотреть все правила вывода из <tex>A_j</tex>: <tex>A_j \to \delta_1 | \ldots | \delta_k</tex>.
заменить каждое правило <tex>A_i \to A_j \gamma</tex> на <tex>A_i \to \delta_1\gamma | \ldots | \delta_k\gamma</tex>.
устранить непосредственную левую рекурсию для <tex>A_i</tex>.
</div>

Если <tex>\varepsilon</tex> присутствовал в языке исходной грамматики, добавим новый начальный символ <tex>S'</tex> и правила <tex>S' \to S \, | \, \varepsilon </tex>.

После <tex>i</tex> итерации внешнего цикла в грамматике будут только правила вида <tex>A_i \to A_j\alpha</tex>, где <tex>j > i</tex>.
Можно заметить, что неравенство становится строгим только после применения алгоритма устранения непосредственной левой рекурсии. При этом добавляются новые нетерминалы. Пусть <tex>{A^\prime}_i </tex> новый нетерминал. Можно заметить, что нет правила вида <tex>\ldots \to {A^\prime}_i</tex>, где <tex>{A^\prime}_i</tex> самый левый нетерминал, а значит новые нетерминалы можно не рассматривать во внешнем цикле.

На <tex>i</tex> итерации внешнего цикла все правила вида <tex>A_i \to A_j \gamma</tex> где <tex> j < i </tex> заменяются на <tex>A_i \to \delta_1\gamma | \ldots | \delta_k\gamma</tex> где <tex>A_j \to \delta_1 | \ldots | \delta_k</tex>. Очевидно, что одна итерация алгоритма не меняет язык, а значит язык получившийся в итоге грамматики совпадает с исходным.

===Асимптотика===
Пусть <tex>a_i</tex> количество правил для нетерминала <tex>A_i</tex>.
Тогда <tex>i</tex> итерация внешнего цикла будет выполняться за <tex>O(\sum\limits_{A_i \to A_j, j < i} a_j) + O(a_i)</tex>, что меньше чем <tex>O(\sum\limits_{i=1}^n a_j)</tex>, значит асимптотика алгоритма <tex>O(n\sum\limits_{i=1}^n a_j)</tex>.

Проблема этого алгоритма в том, что в зависимости от порядка нетерминалов в множестве размер грамматки может получиться экспоненциальным.

Пример грамматики для которой имеет значение порядок нетерминалов

<tex>A_1 \to 0 | 1</tex>

<tex>A_{i+1} \to {A_i}0 | {A_i}1 </tex> для <tex>1 \leq i < n</tex>

Упорядочим множество нетерминалов по возрастанию индексов. Легко заметить, что правила для <tex>A_i</tex> будут представлять из себя все двоичные вектора длины <tex>i</tex>, а значит размер грамматики будет экспоненциальным. Если упорядочить нетерминалы по убыванию в грамматике изменений не будет.

==Пример==
Дана грамматика

<tex>A \to S\alpha </tex>

<tex>S \to S\beta | A\gamma | b</tex>

Среди правил <tex>A</tex> непосредственной рекурсии нет, поэтому во время первой итерации внешнего цикла ничего не происходит.
Во время второй итерации внешнего цикла правило <tex> S \to A\gamma </tex> переходит в <tex> S \to S\alpha\gamma </tex>.

Грамматика имеет вид

<tex>A \to S\alpha </tex>

<tex>S \to{S}{\beta} | {S}{\alpha}{\gamma} | \beta</tex>

Устраняем левую рекурсию для <tex>S</tex>

<tex> S \to\beta{S_1}</tex>

<tex> {S_1} \to\beta{S_1} | \alpha\gamma{S_1}</tex>

==Литература==
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' — '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)
* ''Robert C. Moore'' — [http://aclweb.org/anthology-new/A/A00/A00-2033.pdf Removing Left Recursion from Context-Free Grammars ]

[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]

Устранение левой рекурсии

2013-01-18T19:53:24Z

94.25.229.56: /* Асимптотика */

{{Определение
|definition=Говорят, что [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная (КС) грамматика]] <tex>\Gamma</tex> содержит '''непосредственную левую рекурсию''' (direct left recursion), если она содержит правило вида <tex>A \to A\alpha</tex>.
}}
{{Определение
|definition=Говорят, что КС-грамматика <tex>\Gamma</tex> содержит '''левую рекурсию (left recursion)''', если в ней существует вывод вида <tex>A \Rightarrow^* A\alpha</tex>.
}}

Методы нисходящего разбора (top-down parsers) не в состоянии работать с леворекурсивными грамматиками. Проблема в том, что продукция вида <tex>A \Rightarrow^* A\alpha</tex> может применяться бесконечно долго, так и не выработав некий терминальный символ, который можно было бы сравнить со строкой. Поэтому требуется преобразование грамматики, которое бы устранило левую рекурсию.

==Устранение непосредственной левой рекурсии==
Опишем процедуру, устраняющую все правила вида <tex>A \to A\alpha</tex>, для фиксированного нетерминала <tex>A</tex>.

<ol>
<li>Запишем все правила вывода из <tex>A</tex> в виде:
<tex>A \to A\alpha_1\,|\,\ldots\,|\,A\alpha_n\,|\,\beta_1\,|\,\ldots\,|\,\beta_m </tex>, где
<ul>
<li> <tex>\alpha</tex> {{---}} непустая последовательность терминалов и нетерминалов (<tex>\alpha \nrightarrow \varepsilon </tex>);</li>
<li> <tex>\beta</tex> {{---}} непустая последовательность терминалов и нетерминалов, не начинающаяся с <tex>A</tex>.</li>
</ul>
<li>Заменим правила вывода из <tex>A</tex> на <tex>A \to\beta_1A^\prime\, |\, \ldots\, |\, \beta_mA^\prime \,|\, \beta_1 \,|\, \ldots \,|\, \beta_m</tex>.</li>

<li>Создадим новый нетерминал <tex>{A^\prime} \to \alpha_1{A^\prime}, |\, \ldots\, |\, \alpha_n{A^\prime} | \alpha_1\, |\, \ldots\, |\, \alpha_n</tex>. </li>
</li>
</ol>

Изначально нетерминал <tex>A</tex> порождает сроки вида <tex>\beta\alpha_{i0}\alpha_{i1} \ldots \alpha_{ik}</tex>. В новой грамматике нетерминал <tex>A</tex> порождает <tex>\beta{A^\prime}</tex>, а <tex>A^\prime</tex> порождает строки вида <tex>\alpha_{i0}\alpha_{i1} \ldots \alpha_{ik}</tex>. Из этого очевидно, что изначальная грамматика эквивалентна новой.

===Пример===
<tex>A \to S\alpha | A\alpha</tex>

<tex>S \to A\beta</tex>

Есть непосредственная левая рекурсия <tex>A \to A\alpha</tex>. Добавим нетерминал <tex>A^\prime</tex> и добавим правила <tex>A \to S\alpha{A^{\prime}}</tex>, <tex> A^{\prime} \to \alpha{A^{\prime}} </tex>.

Новая грамматика:

<tex>A \to S\alpha{A^{\prime}} | S\alpha</tex>

<tex>A^{\prime} \to \alpha{A^{\prime}}</tex>

<tex>S \to A\beta</tex>

В новой грамматике нет непосредственной левой рекурсии, но нетерминал <tex>A</tex> леворекурсивен, так как есть <tex> A \Rightarrow S\alpha{A^{\prime}} \Rightarrow A\beta\alpha{A^{\prime}} </tex>

==Алгоритм устранения произвольной левой рекурсии==
Воспользуемся [[Удаление_eps-правил_из_грамматики | алгоритмом удаления <tex> \varepsilon </tex>-правил]]. Получим грамматику без <tex> \varepsilon </tex>-правил для языка <tex>L(\Gamma) \setminus \lbrace \epsilon \rbrace</tex>.

Упорядочим нетерминалы и будим добиваться того, чтобы не было правил вида <tex>A_i \to A_j\alpha</tex>, где <tex>j \le i</tex>.
Если данное условие выполняется для всех<tex>A_i</tex>, то в грамматике нет <tex>A_i \to^* A_i</tex>, а значит не будет левой рекурсии.

Пусть <tex>N = \lbrace A_1, A_2, \ldots , A_n \rbrace</tex> {{---}} упорядоченное множество всех нетерминалов.
<div>
for все нетерминалы <tex>A_i</tex>
for все нетерминалы <tex>A_j</tex>, такие, что <tex> 1 \leq j < i </tex> и
рассмотреть все правила вывода из <tex>A_j</tex>: <tex>A_j \to \delta_1 | \ldots | \delta_k</tex>.
заменить каждое правило <tex>A_i \to A_j \gamma</tex> на <tex>A_i \to \delta_1\gamma | \ldots | \delta_k\gamma</tex>.
устранить непосредственную левую рекурсию для <tex>A_i</tex>.
</div>

Если <tex>\varepsilon</tex> присутствовал в языке исходной грамматики, добавим новый начальный символ <tex>S'</tex> и правила <tex>S' \to S \, | \, \varepsilon </tex>.

После <tex>i</tex> итерации внешнего цикла в грамматике будут только правила вида <tex>A_i \to A_j\alpha</tex>, где <tex>j > i</tex>.
Можно заметить, что неравенство становится строгим только после применения алгоритма устранения непосредственной левой рекурсии. При этом добавляются новые нетерминалы. но так как новые нетерминалы будут ассоциированы только с нетерминалом для которого удаляется непосредственная левая рекурсия их можем не рассматривать в цикле(новый нетерминал не может быть самым левым в каком-либо правиле).

На <tex>i</tex> итерации внешнего цикла все правила вида <tex>A_i \to A_j \gamma</tex> где <tex> j < i </tex> заменяются на <tex>A_i \to \delta_1\gamma | \ldots | \delta_k\gamma</tex> где <tex>A_j \to \delta_1 | \ldots | \delta_k</tex>. Очевидно, что одна итерация алгоритма не меняет язык, а значит язык получившийся в итоге грамматики совпадает с исходным.

===Асимптотика===
Пусть <tex>a_i</tex> количество правил для нетерминала <tex>A_i</tex>.
Тогда <tex>i</tex> итерация внешнего цикла будет выполняться за <tex>O(\sum\limits_{A_i \to A_j, j < i} a_j) + O(a_i)</tex>, что меньше чем <tex>O(\sum\limits_{i=1}^n a_j)</tex>, значит асимптотика алгоритма <tex>O(n\sum\limits_{i=1}^n a_j)</tex>.

Проблема этого алгоритма в том, что в зависимости от порядка нетерминалов в множестве размер грамматки может получиться экспоненциальным.

Пример грамматики для которой имеет значение порядок нетерминалов

<tex>A_1 \to 0 | 1</tex>

<tex>A_{i+1} \to {A_i}0 | {A_i}1 </tex> для <tex>1 \leq i < n</tex>

Упорядочим множество нетерминалов по возрастанию индексов. Легко заметить, что правила для <tex>A_i</tex> будут представлять из себя все двоичные вектора длины <tex>i</tex>, а значит размер грамматики будет экспоненциальным. Если упорядочить нетерминалы по убыванию в грамматике изменений не будет.

==Пример==
Дана грамматика

<tex>A \to S\alpha </tex>

<tex>S \to S\beta | A\gamma | b</tex>

Среди правил <tex>A</tex> непосредственной рекурсии нет, поэтому во время первой итерации внешнего цикла ничего не происходит.
Во время второй итерации внешнего цикла правило <tex> S \to A\gamma </tex> переходит в <tex> S \to S\alpha\gamma </tex>.

Грамматика имеет вид

<tex>A \to S\alpha </tex>

<tex>S \to{S}{\beta} | {S}{\alpha}{\gamma} | \beta</tex>

Устраняем левую рекурсию для <tex>S</tex>

<tex> S \to\beta{S_1}</tex>

<tex> {S_1} \to\beta{S_1} | \alpha\gamma{S_1}</tex>

==Литература==
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' — '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)
* ''Robert C. Moore'' — [http://aclweb.org/anthology-new/A/A00/A00-2033.pdf Removing Left Recursion from Context-Free Grammars ]

[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]

Устранение левой рекурсии

2013-01-18T19:53:07Z

94.25.229.56: /* Асимптотика */

{{Определение
|definition=Говорят, что [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная (КС) грамматика]] <tex>\Gamma</tex> содержит '''непосредственную левую рекурсию''' (direct left recursion), если она содержит правило вида <tex>A \to A\alpha</tex>.
}}
{{Определение
|definition=Говорят, что КС-грамматика <tex>\Gamma</tex> содержит '''левую рекурсию (left recursion)''', если в ней существует вывод вида <tex>A \Rightarrow^* A\alpha</tex>.
}}

Методы нисходящего разбора (top-down parsers) не в состоянии работать с леворекурсивными грамматиками. Проблема в том, что продукция вида <tex>A \Rightarrow^* A\alpha</tex> может применяться бесконечно долго, так и не выработав некий терминальный символ, который можно было бы сравнить со строкой. Поэтому требуется преобразование грамматики, которое бы устранило левую рекурсию.

==Устранение непосредственной левой рекурсии==
Опишем процедуру, устраняющую все правила вида <tex>A \to A\alpha</tex>, для фиксированного нетерминала <tex>A</tex>.

<ol>
<li>Запишем все правила вывода из <tex>A</tex> в виде:
<tex>A \to A\alpha_1\,|\,\ldots\,|\,A\alpha_n\,|\,\beta_1\,|\,\ldots\,|\,\beta_m </tex>, где
<ul>
<li> <tex>\alpha</tex> {{---}} непустая последовательность терминалов и нетерминалов (<tex>\alpha \nrightarrow \varepsilon </tex>);</li>
<li> <tex>\beta</tex> {{---}} непустая последовательность терминалов и нетерминалов, не начинающаяся с <tex>A</tex>.</li>
</ul>
<li>Заменим правила вывода из <tex>A</tex> на <tex>A \to\beta_1A^\prime\, |\, \ldots\, |\, \beta_mA^\prime \,|\, \beta_1 \,|\, \ldots \,|\, \beta_m</tex>.</li>

<li>Создадим новый нетерминал <tex>{A^\prime} \to \alpha_1{A^\prime}, |\, \ldots\, |\, \alpha_n{A^\prime} | \alpha_1\, |\, \ldots\, |\, \alpha_n</tex>. </li>
</li>
</ol>

Изначально нетерминал <tex>A</tex> порождает сроки вида <tex>\beta\alpha_{i0}\alpha_{i1} \ldots \alpha_{ik}</tex>. В новой грамматике нетерминал <tex>A</tex> порождает <tex>\beta{A^\prime}</tex>, а <tex>A^\prime</tex> порождает строки вида <tex>\alpha_{i0}\alpha_{i1} \ldots \alpha_{ik}</tex>. Из этого очевидно, что изначальная грамматика эквивалентна новой.

===Пример===
<tex>A \to S\alpha | A\alpha</tex>

<tex>S \to A\beta</tex>

Есть непосредственная левая рекурсия <tex>A \to A\alpha</tex>. Добавим нетерминал <tex>A^\prime</tex> и добавим правила <tex>A \to S\alpha{A^{\prime}}</tex>, <tex> A^{\prime} \to \alpha{A^{\prime}} </tex>.

Новая грамматика:

<tex>A \to S\alpha{A^{\prime}} | S\alpha</tex>

<tex>A^{\prime} \to \alpha{A^{\prime}}</tex>

<tex>S \to A\beta</tex>

В новой грамматике нет непосредственной левой рекурсии, но нетерминал <tex>A</tex> леворекурсивен, так как есть <tex> A \Rightarrow S\alpha{A^{\prime}} \Rightarrow A\beta\alpha{A^{\prime}} </tex>

==Алгоритм устранения произвольной левой рекурсии==
Воспользуемся [[Удаление_eps-правил_из_грамматики | алгоритмом удаления <tex> \varepsilon </tex>-правил]]. Получим грамматику без <tex> \varepsilon </tex>-правил для языка <tex>L(\Gamma) \setminus \lbrace \epsilon \rbrace</tex>.

Упорядочим нетерминалы и будим добиваться того, чтобы не было правил вида <tex>A_i \to A_j\alpha</tex>, где <tex>j \le i</tex>.
Если данное условие выполняется для всех<tex>A_i</tex>, то в грамматике нет <tex>A_i \to^* A_i</tex>, а значит не будет левой рекурсии.

Пусть <tex>N = \lbrace A_1, A_2, \ldots , A_n \rbrace</tex> {{---}} упорядоченное множество всех нетерминалов.
<div>
for все нетерминалы <tex>A_i</tex>
for все нетерминалы <tex>A_j</tex>, такие, что <tex> 1 \leq j < i </tex> и
рассмотреть все правила вывода из <tex>A_j</tex>: <tex>A_j \to \delta_1 | \ldots | \delta_k</tex>.
заменить каждое правило <tex>A_i \to A_j \gamma</tex> на <tex>A_i \to \delta_1\gamma | \ldots | \delta_k\gamma</tex>.
устранить непосредственную левую рекурсию для <tex>A_i</tex>.
</div>

Если <tex>\varepsilon</tex> присутствовал в языке исходной грамматики, добавим новый начальный символ <tex>S'</tex> и правила <tex>S' \to S \, | \, \varepsilon </tex>.

После <tex>i</tex> итерации внешнего цикла в грамматике будут только правила вида <tex>A_i \to A_j\alpha</tex>, где <tex>j > i</tex>.
Можно заметить, что неравенство становится строгим только после применения алгоритма устранения непосредственной левой рекурсии. При этом добавляются новые нетерминалы. но так как новые нетерминалы будут ассоциированы только с нетерминалом для которого удаляется непосредственная левая рекурсия их можем не рассматривать в цикле(новый нетерминал не может быть самым левым в каком-либо правиле).

На <tex>i</tex> итерации внешнего цикла все правила вида <tex>A_i \to A_j \gamma</tex> где <tex> j < i </tex> заменяются на <tex>A_i \to \delta_1\gamma | \ldots | \delta_k\gamma</tex> где <tex>A_j \to \delta_1 | \ldots | \delta_k</tex>. Очевидно, что одна итерация алгоритма не меняет язык, а значит язык получившийся в итоге грамматики совпадает с исходным.

===Асимптотика===
Пусть <tex>a_i</tex> количество правил для нетерминала <tex>A_i</tex>.
Тогда <tex>i</tex> итерация внешнего цикла будет выполняться за <tex>O(\sum\limits_{A_i \to A_j, j < i} a_j) + O(a_i)</tex>, что меньше чем <tex>O(\sum\limits_{i=1}^n a_j)</tex>, значит асимптотика алгоритма <tex>O(n\sum\limits_{i=1}^n a_j)</tex>.

Проблема этого алгоритма в том, что в зависимости от порядка нетерминалов в множестве размер грамматки может получиться экспоненциальным.

Пример грамматики для которой имеет значение порядок нетерминалов

<tex>A_1 \to 0 | 1</tex>

<tex>A_{i+1} \to {A_i}0 | {A_i}1</tex> для <tex>1 \leq i < n</tex>

Упорядочим множество нетерминалов по возрастанию индексов. Легко заметить, что правила для <tex>A_i</tex> будут представлять из себя все двоичные вектора длины <tex>i</tex>, а значит размер грамматики будет экспоненциальным. Если упорядочить нетерминалы по убыванию в грамматике изменений не будет.

==Пример==
Дана грамматика

<tex>A \to S\alpha </tex>

<tex>S \to S\beta | A\gamma | b</tex>

Среди правил <tex>A</tex> непосредственной рекурсии нет, поэтому во время первой итерации внешнего цикла ничего не происходит.
Во время второй итерации внешнего цикла правило <tex> S \to A\gamma </tex> переходит в <tex> S \to S\alpha\gamma </tex>.

Грамматика имеет вид

<tex>A \to S\alpha </tex>

<tex>S \to{S}{\beta} | {S}{\alpha}{\gamma} | \beta</tex>

Устраняем левую рекурсию для <tex>S</tex>

<tex> S \to\beta{S_1}</tex>

<tex> {S_1} \to\beta{S_1} | \alpha\gamma{S_1}</tex>

==Литература==
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' — '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)
* ''Robert C. Moore'' — [http://aclweb.org/anthology-new/A/A00/A00-2033.pdf Removing Left Recursion from Context-Free Grammars ]

[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]

Устранение левой рекурсии

2013-01-18T19:51:01Z

94.25.229.56: /* Алгоритм устранения произвольной левой рекурсии */

{{Определение
|definition=Говорят, что [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная (КС) грамматика]] <tex>\Gamma</tex> содержит '''непосредственную левую рекурсию''' (direct left recursion), если она содержит правило вида <tex>A \to A\alpha</tex>.
}}
{{Определение
|definition=Говорят, что КС-грамматика <tex>\Gamma</tex> содержит '''левую рекурсию (left recursion)''', если в ней существует вывод вида <tex>A \Rightarrow^* A\alpha</tex>.
}}

Методы нисходящего разбора (top-down parsers) не в состоянии работать с леворекурсивными грамматиками. Проблема в том, что продукция вида <tex>A \Rightarrow^* A\alpha</tex> может применяться бесконечно долго, так и не выработав некий терминальный символ, который можно было бы сравнить со строкой. Поэтому требуется преобразование грамматики, которое бы устранило левую рекурсию.

==Устранение непосредственной левой рекурсии==
Опишем процедуру, устраняющую все правила вида <tex>A \to A\alpha</tex>, для фиксированного нетерминала <tex>A</tex>.

<ol>
<li>Запишем все правила вывода из <tex>A</tex> в виде:
<tex>A \to A\alpha_1\,|\,\ldots\,|\,A\alpha_n\,|\,\beta_1\,|\,\ldots\,|\,\beta_m </tex>, где
<ul>
<li> <tex>\alpha</tex> {{---}} непустая последовательность терминалов и нетерминалов (<tex>\alpha \nrightarrow \varepsilon </tex>);</li>
<li> <tex>\beta</tex> {{---}} непустая последовательность терминалов и нетерминалов, не начинающаяся с <tex>A</tex>.</li>
</ul>
<li>Заменим правила вывода из <tex>A</tex> на <tex>A \to\beta_1A^\prime\, |\, \ldots\, |\, \beta_mA^\prime \,|\, \beta_1 \,|\, \ldots \,|\, \beta_m</tex>.</li>

<li>Создадим новый нетерминал <tex>{A^\prime} \to \alpha_1{A^\prime}, |\, \ldots\, |\, \alpha_n{A^\prime} | \alpha_1\, |\, \ldots\, |\, \alpha_n</tex>. </li>
</li>
</ol>

Изначально нетерминал <tex>A</tex> порождает сроки вида <tex>\beta\alpha_{i0}\alpha_{i1} \ldots \alpha_{ik}</tex>. В новой грамматике нетерминал <tex>A</tex> порождает <tex>\beta{A^\prime}</tex>, а <tex>A^\prime</tex> порождает строки вида <tex>\alpha_{i0}\alpha_{i1} \ldots \alpha_{ik}</tex>. Из этого очевидно, что изначальная грамматика эквивалентна новой.

===Пример===
<tex>A \to S\alpha | A\alpha</tex>

<tex>S \to A\beta</tex>

Есть непосредственная левая рекурсия <tex>A \to A\alpha</tex>. Добавим нетерминал <tex>A^\prime</tex> и добавим правила <tex>A \to S\alpha{A^{\prime}}</tex>, <tex> A^{\prime} \to \alpha{A^{\prime}} </tex>.

Новая грамматика:

<tex>A \to S\alpha{A^{\prime}} | S\alpha</tex>

<tex>A^{\prime} \to \alpha{A^{\prime}}</tex>

<tex>S \to A\beta</tex>

В новой грамматике нет непосредственной левой рекурсии, но нетерминал <tex>A</tex> леворекурсивен, так как есть <tex> A \Rightarrow S\alpha{A^{\prime}} \Rightarrow A\beta\alpha{A^{\prime}} </tex>

==Алгоритм устранения произвольной левой рекурсии==
Воспользуемся [[Удаление_eps-правил_из_грамматики | алгоритмом удаления <tex> \varepsilon </tex>-правил]]. Получим грамматику без <tex> \varepsilon </tex>-правил для языка <tex>L(\Gamma) \setminus \lbrace \epsilon \rbrace</tex>.

Упорядочим нетерминалы и будим добиваться того, чтобы не было правил вида <tex>A_i \to A_j\alpha</tex>, где <tex>j \le i</tex>.
Если данное условие выполняется для всех<tex>A_i</tex>, то в грамматике нет <tex>A_i \to^* A_i</tex>, а значит не будет левой рекурсии.

Пусть <tex>N = \lbrace A_1, A_2, \ldots , A_n \rbrace</tex> {{---}} упорядоченное множество всех нетерминалов.
<div>
for все нетерминалы <tex>A_i</tex>
for все нетерминалы <tex>A_j</tex>, такие, что <tex> 1 \leq j < i </tex> и
рассмотреть все правила вывода из <tex>A_j</tex>: <tex>A_j \to \delta_1 | \ldots | \delta_k</tex>.
заменить каждое правило <tex>A_i \to A_j \gamma</tex> на <tex>A_i \to \delta_1\gamma | \ldots | \delta_k\gamma</tex>.
устранить непосредственную левую рекурсию для <tex>A_i</tex>.
</div>

Если <tex>\varepsilon</tex> присутствовал в языке исходной грамматики, добавим новый начальный символ <tex>S'</tex> и правила <tex>S' \to S \, | \, \varepsilon </tex>.

После <tex>i</tex> итерации внешнего цикла в грамматике будут только правила вида <tex>A_i \to A_j\alpha</tex>, где <tex>j > i</tex>.
Можно заметить, что неравенство становится строгим только после применения алгоритма устранения непосредственной левой рекурсии. При этом добавляются новые нетерминалы. но так как новые нетерминалы будут ассоциированы только с нетерминалом для которого удаляется непосредственная левая рекурсия их можем не рассматривать в цикле(новый нетерминал не может быть самым левым в каком-либо правиле).

На <tex>i</tex> итерации внешнего цикла все правила вида <tex>A_i \to A_j \gamma</tex> где <tex> j < i </tex> заменяются на <tex>A_i \to \delta_1\gamma | \ldots | \delta_k\gamma</tex> где <tex>A_j \to \delta_1 | \ldots | \delta_k</tex>. Очевидно, что одна итерация алгоритма не меняет язык, а значит язык получившийся в итоге грамматики совпадает с исходным.

===Асимптотика===
Пусть <tex>a_i</tex> количество правил для нетерминала <tex>A_i</tex>.
Тогда <tex>i</tex> итерация внешнего цикла будет выполняться за <tex>O(\sum\limits_{A_i \to A_j, j < i} a_j) + O(a_i)</tex>, что меньше чем <tex>O(\sum\limits_{i=1}^n a_j)</tex>, значит асимптотика алгоритма <tex>O(n\sum\limits_{i=1}^n a_j)</tex>.

Проблема этого алгоритма в том, что в зависимости от порядка нетерминалов в множестве размер грамматки может получиться экспоненциальным.

Пример грамматики для которой имеет значение порядок нетерминалов

<tex>A_1 \to 0 | 1</tex>

<tex>A_{i+1} \to {A_i}0</tex> для <tex>1 \leq i < n</tex>

Упорядочим множество нетерминалов по возрастанию индексов. Легко заметить, что правила для <tex>A_i</tex> будут представлять из себя все двоичные вектора длины <tex>i</tex>, а значит размер грамматики будет экспоненциальным. Если упорядочить нетерминалы по убыванию в грамматике изменений не будет.

==Пример==
Дана грамматика

<tex>A \to S\alpha </tex>

<tex>S \to S\beta | A\gamma | b</tex>

Среди правил <tex>A</tex> непосредственной рекурсии нет, поэтому во время первой итерации внешнего цикла ничего не происходит.
Во время второй итерации внешнего цикла правило <tex> S \to A\gamma </tex> переходит в <tex> S \to S\alpha\gamma </tex>.

Грамматика имеет вид

<tex>A \to S\alpha </tex>

<tex>S \to{S}{\beta} | {S}{\alpha}{\gamma} | \beta</tex>

Устраняем левую рекурсию для <tex>S</tex>

<tex> S \to\beta{S_1}</tex>

<tex> {S_1} \to\beta{S_1} | \alpha\gamma{S_1}</tex>

==Литература==
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' — '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)
* ''Robert C. Moore'' — [http://aclweb.org/anthology-new/A/A00/A00-2033.pdf Removing Left Recursion from Context-Free Grammars ]

[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]

Устранение левой рекурсии

2013-01-18T19:50:31Z

94.25.229.56: /* Алгоритм устранения произвольной левой рекурсии */

{{Определение
|definition=Говорят, что [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная (КС) грамматика]] <tex>\Gamma</tex> содержит '''непосредственную левую рекурсию''' (direct left recursion), если она содержит правило вида <tex>A \to A\alpha</tex>.
}}
{{Определение
|definition=Говорят, что КС-грамматика <tex>\Gamma</tex> содержит '''левую рекурсию (left recursion)''', если в ней существует вывод вида <tex>A \Rightarrow^* A\alpha</tex>.
}}

Методы нисходящего разбора (top-down parsers) не в состоянии работать с леворекурсивными грамматиками. Проблема в том, что продукция вида <tex>A \Rightarrow^* A\alpha</tex> может применяться бесконечно долго, так и не выработав некий терминальный символ, который можно было бы сравнить со строкой. Поэтому требуется преобразование грамматики, которое бы устранило левую рекурсию.

==Устранение непосредственной левой рекурсии==
Опишем процедуру, устраняющую все правила вида <tex>A \to A\alpha</tex>, для фиксированного нетерминала <tex>A</tex>.

<ol>
<li>Запишем все правила вывода из <tex>A</tex> в виде:
<tex>A \to A\alpha_1\,|\,\ldots\,|\,A\alpha_n\,|\,\beta_1\,|\,\ldots\,|\,\beta_m </tex>, где
<ul>
<li> <tex>\alpha</tex> {{---}} непустая последовательность терминалов и нетерминалов (<tex>\alpha \nrightarrow \varepsilon </tex>);</li>
<li> <tex>\beta</tex> {{---}} непустая последовательность терминалов и нетерминалов, не начинающаяся с <tex>A</tex>.</li>
</ul>
<li>Заменим правила вывода из <tex>A</tex> на <tex>A \to\beta_1A^\prime\, |\, \ldots\, |\, \beta_mA^\prime \,|\, \beta_1 \,|\, \ldots \,|\, \beta_m</tex>.</li>

<li>Создадим новый нетерминал <tex>{A^\prime} \to \alpha_1{A^\prime}, |\, \ldots\, |\, \alpha_n{A^\prime} | \alpha_1\, |\, \ldots\, |\, \alpha_n</tex>. </li>
</li>
</ol>

Изначально нетерминал <tex>A</tex> порождает сроки вида <tex>\beta\alpha_{i0}\alpha_{i1} \ldots \alpha_{ik}</tex>. В новой грамматике нетерминал <tex>A</tex> порождает <tex>\beta{A^\prime}</tex>, а <tex>A^\prime</tex> порождает строки вида <tex>\alpha_{i0}\alpha_{i1} \ldots \alpha_{ik}</tex>. Из этого очевидно, что изначальная грамматика эквивалентна новой.

===Пример===
<tex>A \to S\alpha | A\alpha</tex>

<tex>S \to A\beta</tex>

Есть непосредственная левая рекурсия <tex>A \to A\alpha</tex>. Добавим нетерминал <tex>A^\prime</tex> и добавим правила <tex>A \to S\alpha{A^{\prime}}</tex>, <tex> A^{\prime} \to \alpha{A^{\prime}} </tex>.

Новая грамматика:

<tex>A \to S\alpha{A^{\prime}} | S\alpha</tex>

<tex>A^{\prime} \to \alpha{A^{\prime}}</tex>

<tex>S \to A\beta</tex>

В новой грамматике нет непосредственной левой рекурсии, но нетерминал <tex>A</tex> леворекурсивен, так как есть <tex> A \Rightarrow S\alpha{A^{\prime}} \Rightarrow A\beta\alpha{A^{\prime}} </tex>

==Алгоритм устранения произвольной левой рекурсии==
Воспользуемся [[Удаление_eps-правил_из_грамматики | алгоритмом удаления <tex> \varepsilon </tex>-правил]]. Получим грамматику без <tex> \varepsilon </tex>-правил для языка <tex>L(\Gamma) \setminus \lbrace \epsilon \rbrace</tex>.

Упорядочим нетерминалы и будим добиваться того, чтобы не было правил вида <tex>A_i \to A_j\alpha</tex>, где <tex>j \le i</tex>.
Если данное условие выполняется для всех<tex>A_i</tex>, то в грамматике нет <tex>A_i \to^* A_i</tex>, а значит не будет левой рекурсии.

Пусть <tex>N = \lbrace A_1, A_2, \ldots , A_n \rbrace</tex> {{---}} упорядоченное множество всех нетерминалов.
<div>
for все нетерминалы <tex>A_i</tex>
for все нетерминалы <tex>A_j</tex>, такие, что <tex> 1 \leq j < i </tex> и
рассмотреть все правила вывода из <tex>A_j</tex>: <tex>A_j \to \delta_1 | \ldots | \delta_k</tex>.
заменить каждое правило <tex>A_i \to A_j \gamma</tex> на <tex>A_i \to \delta_1\gamma | \ldots | \delta_k\gamma</tex>.
устранить непосредственную левую рекурсию для <tex>A_i</tex>.
</div>

Если <tex>\varepsilon</tex> присутствовал в языке исходной грамматики, добавим новый начальный символ <tex>S'</tex> и правила <tex>S' \to S \, | \, \varepsilon </tex>.

После <tex>i</tex> итерации внешнего цикла в грамматике будут только правила вида <tex>A_i \to A_j\alpha</tex>, где <tex>j > i</tex>.
Можно заметить, что неравенство становится строгим только после применения алгоритма устранения непосредственной левой рекурсии. При этом добавляются новые нетерминалы. но так как новые нетерминалы будут ассоциированы только с нетерминалом для которого удаляется непосредственная левая рекурсия их можем не рассматривать в цикле(новый нетерминал не может быть самым левым в каком-либо правиле).

===Пример

На <tex>i</tex> итерации внешнего цикла все правила вида <tex>A_i \to A_j \gamma</tex> где <tex> j < i </tex> заменяются на <tex>A_i \to \delta_1\gamma | \ldots | \delta_k\gamma</tex> где <tex>A_j \to \delta_1 | \ldots | \delta_k</tex>. Очевидно, что одна итерация алгоритма не меняет язык, а значит язык получившийся в итоге грамматики совпадает с исходным.

===Асимптотика===
Пусть <tex>a_i</tex> количество правил для нетерминала <tex>A_i</tex>.
Тогда <tex>i</tex> итерация внешнего цикла будет выполняться за <tex>O(\sum\limits_{A_i \to A_j, j < i} a_j) + O(a_i)</tex>, что меньше чем <tex>O(\sum\limits_{i=1}^n a_j)</tex>, значит асимптотика алгоритма <tex>O(n\sum\limits_{i=1}^n a_j)</tex>.

Проблема этого алгоритма в том, что в зависимости от порядка нетерминалов в множестве размер грамматки может получиться экспоненциальным.

Пример грамматики для которой имеет значение порядок нетерминалов

<tex>A_1 \to 0 | 1</tex>

<tex>A_{i+1} \to {A_i}0</tex> для <tex>1 \leq i < n</tex>

Упорядочим множество нетерминалов по возрастанию индексов. Легко заметить, что правила для <tex>A_i</tex> будут представлять из себя все двоичные вектора длины <tex>i</tex>, а значит размер грамматики будет экспоненциальным. Если упорядочить нетерминалы по убыванию в грамматике изменений не будет.

==Пример==
Дана грамматика

<tex>A \to S\alpha </tex>

<tex>S \to S\beta | A\gamma | b</tex>

Среди правил <tex>A</tex> непосредственной рекурсии нет, поэтому во время первой итерации внешнего цикла ничего не происходит.
Во время второй итерации внешнего цикла правило <tex> S \to A\gamma </tex> переходит в <tex> S \to S\alpha\gamma </tex>.

Грамматика имеет вид

<tex>A \to S\alpha </tex>

<tex>S \to{S}{\beta} | {S}{\alpha}{\gamma} | \beta</tex>

Устраняем левую рекурсию для <tex>S</tex>

<tex> S \to\beta{S_1}</tex>

<tex> {S_1} \to\beta{S_1} | \alpha\gamma{S_1}</tex>

==Литература==
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' — '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)
* ''Robert C. Moore'' — [http://aclweb.org/anthology-new/A/A00/A00-2033.pdf Removing Left Recursion from Context-Free Grammars ]

[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]

Устранение левой рекурсии

2013-01-18T19:34:18Z

94.25.229.56: /* Алгоритм устранения произвольной левой рекурсии */

{{Определение
|definition=Говорят, что [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная (КС) грамматика]] <tex>\Gamma</tex> содержит '''непосредственную левую рекурсию''' (direct left recursion), если она содержит правило вида <tex>A \to A\alpha</tex>.
}}
{{Определение
|definition=Говорят, что КС-грамматика <tex>\Gamma</tex> содержит '''левую рекурсию (left recursion)''', если в ней существует вывод вида <tex>A \Rightarrow^* A\alpha</tex>.
}}

Методы нисходящего разбора (top-down parsers) не в состоянии работать с леворекурсивными грамматиками. Проблема в том, что продукция вида <tex>A \Rightarrow^* A\alpha</tex> может применяться бесконечно долго, так и не выработав некий терминальный символ, который можно было бы сравнить со строкой. Поэтому требуется преобразование грамматики, которое бы устранило левую рекурсию.

==Устранение непосредственной левой рекурсии==
Опишем процедуру, устраняющую все правила вида <tex>A \to A\alpha</tex>, для фиксированного нетерминала <tex>A</tex>.

<ol>
<li>Запишем все правила вывода из <tex>A</tex> в виде:
<tex>A \to A\alpha_1\,|\,\ldots\,|\,A\alpha_n\,|\,\beta_1\,|\,\ldots\,|\,\beta_m </tex>, где
<ul>
<li> <tex>\alpha</tex> {{---}} непустая последовательность терминалов и нетерминалов (<tex>\alpha \nrightarrow \varepsilon </tex>);</li>
<li> <tex>\beta</tex> {{---}} непустая последовательность терминалов и нетерминалов, не начинающаяся с <tex>A</tex>.</li>
</ul>
<li>Заменим правила вывода из <tex>A</tex> на <tex>A \to\beta_1A^\prime\, |\, \ldots\, |\, \beta_mA^\prime \,|\, \beta_1 \,|\, \ldots \,|\, \beta_m</tex>.</li>

<li>Создадим новый нетерминал <tex>{A^\prime} \to \alpha_1{A^\prime}, |\, \ldots\, |\, \alpha_n{A^\prime} | \alpha_1\, |\, \ldots\, |\, \alpha_n</tex>. </li>
</li>
</ol>

Изначально нетерминал <tex>A</tex> порождает сроки вида <tex>\beta\alpha_{i0}\alpha_{i1} \ldots \alpha_{ik}</tex>. В новой грамматике нетерминал <tex>A</tex> порождает <tex>\beta{A^\prime}</tex>, а <tex>A^\prime</tex> порождает строки вида <tex>\alpha_{i0}\alpha_{i1} \ldots \alpha_{ik}</tex>. Из этого очевидно, что изначальная грамматика эквивалентна новой.

===Пример===
<tex>A \to S\alpha | A\alpha</tex>

<tex>S \to A\beta</tex>

Есть непосредственная левая рекурсия <tex>A \to A\alpha</tex>. Добавим нетерминал <tex>A^\prime</tex> и добавим правила <tex>A \to S\alpha{A^{\prime}}</tex>, <tex> A^{\prime} \to \alpha{A^{\prime}} </tex>.

Новая грамматика:

<tex>A \to S\alpha{A^{\prime}} | S\alpha</tex>

<tex>A^{\prime} \to \alpha{A^{\prime}}</tex>

<tex>S \to A\beta</tex>

В новой грамматике нет непосредственной левой рекурсии, но нетерминал <tex>A</tex> леворекурсивен, так как есть <tex> A \Rightarrow S\alpha{A^{\prime}} \Rightarrow A\beta\alpha{A^{\prime}} </tex>

==Алгоритм устранения произвольной левой рекурсии==
Воспользуемся [[Удаление_eps-правил_из_грамматики | алгоритмом удаления <tex> \varepsilon </tex>-правил]]. Получим грамматику без <tex> \varepsilon </tex>-правил для языка <tex>L(\Gamma) \setminus \lbrace \epsilon \rbrace</tex>.

Упорядочим нетерминалы и будим добиваться того, чтобы не было правил вида <tex>A_i \to A_j\alpha</tex>, где <tex>j \le i</tex>.
Если данное условие выполняется для всех<tex>A_i</tex>, то в грамматике нет <tex>A_i \to^* A_i</tex>, а значит не будет левой рекурсии.

Пусть <tex>N = \lbrace A_1, A_2, \ldots , A_n \rbrace</tex> {{---}} упорядоченное множество всех нетерминалов.
<div>
for все нетерминалы <tex>A_i</tex>
for все нетерминалы <tex>A_j</tex>, такие, что <tex> 1 \leq j < i </tex> и
рассмотреть все правила вывода из <tex>A_j</tex>: <tex>A_j \to \delta_1 | \ldots | \delta_k</tex>.
заменить каждое правило <tex>A_i \to A_j \gamma</tex> на <tex>A_i \to \delta_1\gamma | \ldots | \delta_k\gamma</tex>.
устранить непосредственную левую рекурсию для <tex>A_i</tex>.
</div>

Если <tex>\varepsilon</tex> присутствовал в языке исходной грамматики, добавим новый начальный символ <tex>S'</tex> и правила <tex>S' \to S \, | \, \varepsilon </tex>.

После <tex>i</tex> итерации внешнего цикла в грамматике будут только правила вида <tex>A_i \to A_j\alpha</tex>, где <tex>j > i</tex>.
Можно заметить, что неравенство становится строгим только после применения алгоритма устранения непосредственной левой рекурсии. При этом добавляются новые нетерминалы, но по очевидным соображениям их можно не рассматривать в цикле.

На <tex>i</tex> итерации внешнего цикла все правила вида <tex>A_i \to A_j \gamma</tex> где <tex> j < i </tex> заменяются на <tex>A_i \to \delta_1\gamma | \ldots | \delta_k\gamma</tex> где <tex>A_j \to \delta_1 | \ldots | \delta_k</tex>. Очевидно, что одна итерация алгоритма не меняет язык, а значит язык получившийся в итоге грамматики совпадает с исходным.

===Асимптотика===
Пусть <tex>a_i</tex> количество правил для нетерминала <tex>A_i</tex>.
Тогда <tex>i</tex> итерация внешнего цикла будет выполняться за <tex>O(\sum\limits_{A_i \to A_j, j < i} a_j) + O(a_i)</tex>, что меньше чем <tex>O(\sum\limits_{i=1}^n a_j)</tex>, значит асимптотика алгоритма <tex>O(n\sum\limits_{i=1}^n a_j)</tex>.

Проблема этого алгоритма в том, что в зависимости от порядка нетерминалов в множестве размер грамматки может получиться экспоненциальным.

Пример грамматики для которой имеет значение порядок нетерминалов

<tex>A_1 \to 0 | 1</tex>

<tex>A_{i+1} \to {A_i}0</tex> для <tex>1 \leq i < n</tex>

Упорядочим множество нетерминалов по возрастанию индексов. Легко заметить, что правила для <tex>A_i</tex> будут представлять из себя все двоичные вектора длины <tex>i</tex>, а значит размер грамматики будет экспоненциальным. Если упорядочить нетерминалы по убыванию в грамматике изменений не будет.

==Пример==
Дана грамматика

<tex>A \to S\alpha </tex>

<tex>S \to S\beta | A\gamma | b</tex>

Среди правил <tex>A</tex> непосредственной рекурсии нет, поэтому во время первой итерации внешнего цикла ничего не происходит.
Во время второй итерации внешнего цикла правило <tex> S \to A\gamma </tex> переходит в <tex> S \to S\alpha\gamma </tex>.

Грамматика имеет вид

<tex>A \to S\alpha </tex>

<tex>S \to{S}{\beta} | {S}{\alpha}{\gamma} | \beta</tex>

Устраняем левую рекурсию для <tex>S</tex>

<tex> S \to\beta{S_1}</tex>

<tex> {S_1} \to\beta{S_1} | \alpha\gamma{S_1}</tex>

==Литература==
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' — '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)
* ''Robert C. Moore'' — [http://aclweb.org/anthology-new/A/A00/A00-2033.pdf Removing Left Recursion from Context-Free Grammars ]

[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]

Устранение левой рекурсии

2013-01-18T18:59:09Z

94.25.229.56: /* Алгоритм устранения произвольной левой рекурсии */

{{Определение
|definition=Говорят, что [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная (КС) грамматика]] <tex>\Gamma</tex> содержит '''непосредственную левую рекурсию''' (direct left recursion), если она содержит правило вида <tex>A \to A\alpha</tex>.
}}
{{Определение
|definition=Говорят, что КС-грамматика <tex>\Gamma</tex> содержит '''левую рекурсию (left recursion)''', если в ней существует вывод вида <tex>A \Rightarrow^* A\alpha</tex>.
}}

Методы нисходящего разбора (top-down parsers) не в состоянии работать с леворекурсивными грамматиками. Проблема в том, что продукция вида <tex>A \Rightarrow^* A\alpha</tex> может применяться бесконечно долго, так и не выработав некий терминальный символ, который можно было бы сравнить со строкой. Поэтому требуется преобразование грамматики, которое бы устранило левую рекурсию.

==Устранение непосредственной левой рекурсии==
Опишем процедуру, устраняющую все правила вида <tex>A \to A\alpha</tex>, для фиксированного нетерминала <tex>A</tex>.

<ol>
<li>Запишем все правила вывода из <tex>A</tex> в виде:
<tex>A \to A\alpha_1\,|\,\ldots\,|\,A\alpha_n\,|\,\beta_1\,|\,\ldots\,|\,\beta_m </tex>, где
<ul>
<li> <tex>\alpha</tex> {{---}} непустая последовательность терминалов и нетерминалов (<tex>\alpha \nrightarrow \varepsilon </tex>);</li>
<li> <tex>\beta</tex> {{---}} непустая последовательность терминалов и нетерминалов, не начинающаяся с <tex>A</tex>.</li>
</ul>
<li>Заменим правила вывода из <tex>A</tex> на <tex>A \to\beta_1A^\prime\, |\, \ldots\, |\, \beta_mA^\prime \,|\, \beta_1 \,|\, \ldots \,|\, \beta_m</tex>.</li>

<li>Создадим новый нетерминал <tex>{A^\prime} \to \alpha_1{A^\prime}, |\, \ldots\, |\, \alpha_n{A^\prime} | \alpha_1\, |\, \ldots\, |\, \alpha_n</tex>. </li>
</li>
</ol>

Изначально нетерминал <tex>A</tex> порождает сроки вида <tex>\beta\alpha_{i0}\alpha_{i1} \ldots \alpha_{ik}</tex>. В новой грамматике нетерминал <tex>A</tex> порождает <tex>\beta{A^\prime}</tex>, а <tex>A^\prime</tex> порождает строки вида <tex>\alpha_{i0}\alpha_{i1} \ldots \alpha_{ik}</tex>. Из этого очевидно, что изначальная грамматика эквивалентна новой.

===Пример===
<tex>A \to S\alpha | A\alpha</tex>

<tex>S \to A\beta</tex>

Есть непосредственная левая рекурсия <tex>A \to A\alpha</tex>. Добавим нетерминал <tex>A^\prime</tex> и добавим правила <tex>A \to S\alpha{A^{\prime}}</tex>, <tex> A^{\prime} \to \alpha{A^{\prime}} </tex>.

Новая грамматика:

<tex>A \to S\alpha{A^{\prime}} | S\alpha</tex>

<tex>A^{\prime} \to \alpha{A^{\prime}}</tex>

<tex>S \to A\beta</tex>

В новой грамматике нет непосредственной левой рекурсии, но нетерминал <tex>A</tex> леворекурсивен, так как есть <tex> A \Rightarrow S\alpha{A^{\prime}} \Rightarrow A\beta\alpha{A^{\prime}} </tex>

==Алгоритм устранения произвольной левой рекурсии==
Воспользуемся [[Удаление_eps-правил_из_грамматики | алгоритмом удаления <tex> \varepsilon </tex>-правил]]. Получим грамматику без <tex> \varepsilon </tex>-правил для языка <tex>L(\Gamma) \setminus \lbrace \epsilon \rbrace</tex>.

Упорядочим нетерминалы и будим добиваться того, чтобы не было правил вида <tex>A_i \to A_j\alpha</tex>, где <tex>j \le i</tex>.
Можно заметить, что если данное условие выполняется для всех<tex>A_i</tex>, то в грамматике не будет <tex>A_i \to^* A_i</tex>, а значит надо будет только устранить непосредственную левую рекурсию для <tex>A_i</tex>.

Пусть <tex>N = \lbrace A_1, A_2, \ldots , A_n \rbrace</tex> {{---}} упорядоченное множество всех нетерминалов.
<div>
for все нетерминалы <tex>A_i</tex>
for все нетерминалы <tex>A_j</tex>, такие, что <tex> 1 \leq j < i </tex> и
рассмотреть все правила вывода из <tex>A_j</tex>: <tex>A_j \to \delta_1 | \ldots | \delta_k</tex>.
заменить каждое правило <tex>A_i \to A_j \gamma</tex> на <tex>A_i \to \delta_1\gamma | \ldots | \delta_k\gamma</tex>.
устранить непосредственную левую рекурсию для <tex>A_i</tex>.
</div>

Если <tex>\varepsilon</tex> присутствовал в языке исходной грамматики, добавим новый начальный символ <tex>S'</tex> и правила <tex>S' \to S \, | \, \varepsilon </tex>.

На <tex>i</tex> итерации внешнего цикла все правила вида <tex>A_i \to A_j \gamma</tex> где <tex> j < i </tex> заменяются на <tex>A_i \to \delta_1\gamma | \ldots | \delta_k\gamma</tex> где <tex>A_j \to \delta_1 | \ldots | \delta_k</tex>. Очевидно, что одна итерация алгоритма не меняет язык, а значит язык получившийся в итоге грамматики совпадает с исходным.

===Асимптотика===
Пусть <tex>a_i</tex> количество правил для нетерминала <tex>A_i</tex>.
Тогда <tex>i</tex> итерация внешнего цикла будет выполняться за <tex>O(\sum\limits_{A_i \to A_j, j < i} a_j) + O(a_i)</tex>, что меньше чем <tex>O(\sum\limits_{i=1}^n a_j)</tex>, значит асимптотика алгоритма <tex>O(n\sum\limits_{i=1}^n a_j)</tex>.

Проблема этого алгоритма в том, что в зависимости от порядка нетерминалов в множестве размер грамматки может получиться экспоненциальным.

Пример грамматики для которой имеет значение порядок нетерминалов

<tex>A_1 \to 0 | 1</tex>

<tex>A_{i+1} \to {A_i}0</tex> для <tex>1 \leq i < n</tex>

Упорядочим множество нетерминалов по возрастанию индексов. Легко заметить, что правила для <tex>A_i</tex> будут представлять из себя все двоичные вектора длины <tex>i</tex>, а значит размер грамматики будет экспоненциальным. Если упорядочить нетерминалы по убыванию в грамматике изменений не будет.

==Пример==
Дана грамматика

<tex>A \to S\alpha </tex>

<tex>S \to S\beta | A\gamma | b</tex>

Среди правил <tex>A</tex> непосредственной рекурсии нет, поэтому во время первой итерации внешнего цикла ничего не происходит.
Во время второй итерации внешнего цикла правило <tex> S \to A\gamma </tex> переходит в <tex> S \to S\alpha\gamma </tex>.

Грамматика имеет вид

<tex>A \to S\alpha </tex>

<tex>S \to{S}{\beta} | {S}{\alpha}{\gamma} | \beta</tex>

Устраняем левую рекурсию для <tex>S</tex>

<tex> S \to\beta{S_1}</tex>

<tex> {S_1} \to\beta{S_1} | \alpha\gamma{S_1}</tex>

==Литература==
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' — '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)
* ''Robert C. Moore'' — [http://aclweb.org/anthology-new/A/A00/A00-2033.pdf Removing Left Recursion from Context-Free Grammars ]

[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]

Устранение левой рекурсии

2013-01-18T18:32:43Z

94.25.229.56: /* Алгоритм устранения произвольной левой рекурсии */

{{Определение
|definition=Говорят, что [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная (КС) грамматика]] <tex>\Gamma</tex> содержит '''непосредственную левую рекурсию''' (direct left recursion), если она содержит правило вида <tex>A \to A\alpha</tex>.
}}
{{Определение
|definition=Говорят, что КС-грамматика <tex>\Gamma</tex> содержит '''левую рекурсию (left recursion)''', если в ней существует вывод вида <tex>A \Rightarrow^* A\alpha</tex>.
}}

Методы нисходящего разбора (top-down parsers) не в состоянии работать с леворекурсивными грамматиками. Проблема в том, что продукция вида <tex>A \Rightarrow^* A\alpha</tex> может применяться бесконечно долго, так и не выработав некий терминальный символ, который можно было бы сравнить со строкой. Поэтому требуется преобразование грамматики, которое бы устранило левую рекурсию.

==Устранение непосредственной левой рекурсии==
Опишем процедуру, устраняющую все правила вида <tex>A \to A\alpha</tex>, для фиксированного нетерминала <tex>A</tex>.

<ol>
<li>Запишем все правила вывода из <tex>A</tex> в виде:
<tex>A \to A\alpha_1\,|\,\ldots\,|\,A\alpha_n\,|\,\beta_1\,|\,\ldots\,|\,\beta_m </tex>, где
<ul>
<li> <tex>\alpha</tex> {{---}} непустая последовательность терминалов и нетерминалов (<tex>\alpha \nrightarrow \varepsilon </tex>);</li>
<li> <tex>\beta</tex> {{---}} непустая последовательность терминалов и нетерминалов, не начинающаяся с <tex>A</tex>.</li>
</ul>
<li>Заменим правила вывода из <tex>A</tex> на <tex>A \to\beta_1A^\prime\, |\, \ldots\, |\, \beta_mA^\prime \,|\, \beta_1 \,|\, \ldots \,|\, \beta_m</tex>.</li>

<li>Создадим новый нетерминал <tex>{A^\prime} \to \alpha_1{A^\prime}, |\, \ldots\, |\, \alpha_n{A^\prime} | \alpha_1\, |\, \ldots\, |\, \alpha_n</tex>. </li>
</li>
</ol>

Изначально нетерминал <tex>A</tex> порождает сроки вида <tex>\beta\alpha_{i0}\alpha_{i1} \ldots \alpha_{ik}</tex>. В новой грамматике нетерминал <tex>A</tex> порождает <tex>\beta{A^\prime}</tex>, а <tex>A^\prime</tex> порождает строки вида <tex>\alpha_{i0}\alpha_{i1} \ldots \alpha_{ik}</tex>. Из этого очевидно, что изначальная грамматика эквивалентна новой.

===Пример===
<tex>A \to S\alpha | A\alpha</tex>

<tex>S \to A\beta</tex>

Есть непосредственная левая рекурсия <tex>A \to A\alpha</tex>. Добавим нетерминал <tex>A^\prime</tex> и добавим правила <tex>A \to S\alpha{A^{\prime}}</tex>, <tex> A^{\prime} \to \alpha{A^{\prime}} </tex>.

Новая грамматика:

<tex>A \to S\alpha{A^{\prime}} | S\alpha</tex>

<tex>A^{\prime} \to \alpha{A^{\prime}}</tex>

<tex>S \to A\beta</tex>

В новой грамматике нет непосредственной левой рекурсии, но нетерминал <tex>A</tex> леворекурсивен, так как есть <tex> A \Rightarrow S\alpha{A^{\prime}} \Rightarrow A\beta\alpha{A^{\prime}} </tex>

==Алгоритм устранения произвольной левой рекурсии==
Воспользуемся [[Удаление_eps-правил_из_грамматики | алгоритмом удаления <tex> \varepsilon </tex>-правил]]. Получим грамматику без <tex> \varepsilon </tex>-правил для языка <tex>L(\Gamma) \setminus \lbrace \epsilon \rbrace</tex>.

Упорядочим нетерминалы и будим добиваться того, чтобы не было правил вида <tex>A_i \to A_j\alpha</tex>, где <tex>j \le i</tex>.
Можно заметить, что если данное условие выполняется для всех<tex>A_i</tex>, то в грамматике не будет <tex>A_i \to^* A_i</tex>, а значит надо будет только устранить непосредственную левую рекурсию для <tex>A_i</tex>.

Пусть <tex>N = \lbrace A_1, A_2, \ldots , A_n \rbrace</tex> {{---}} упорядоченное множество всех нетерминалов.
<div>
for все нетерминалы <tex>A_i</tex>
for все нетерминалы <tex>A_j</tex>, такие, что <tex> 1 \leq j < i </tex> и
рассмотреть все правила вывода из <tex>A_j</tex>: <tex>A_j \to \delta_1 | \ldots | \delta_k</tex>.
заменить каждое правило <tex>A_i \to A_j \gamma</tex> на <tex>A_i \to \delta_1\gamma | \ldots | \delta_k\gamma</tex>.
устранить непосредственную левую рекурсию для <tex>A_i</tex>.
</div>

Если <tex>\varepsilon</tex> присутствовал в языке исходной грамматики, добавим новый начальный символ <tex>S'</tex> и правила <tex>S' \to S \, | \, \varepsilon </tex>.

На <tex>i</tex> итерации внешнего цикла все правила вида <tex>A_i \to A_j \gamma</tex> где <tex> j < i </tex> заменяются на <tex>A_i \to \delta_1\gamma | \ldots | \delta_k\gamma</tex> где <tex>A_j \to \delta_1 | \ldots | \delta_k</tex>. Таким образом остается только избавиться от непосредственной рекурсии для <tex>A_i</tex>.
Очевидно, что одна итерация алгоритма не меняет язык, а значит язык получившийся в итоге грамматики совпадает с исходным.

===Асимптотика===
Пусть <tex>a_i</tex> количество правил для нетерминала <tex>A_i</tex>.
Тогда <tex>i</tex> итерация внешнего цикла будет выполняться за <tex>O(\sum\limits_{A_i \to A_j, j < i} a_j) + O(a_i)</tex>, что меньше чем <tex>O(\sum\limits_{i=1}^n a_j)</tex>, значит асимптотика алгоритма <tex>O(n\sum\limits_{i=1}^n a_j)</tex>.

Проблема этого алгоритма в том, что в зависимости от порядка нетерминалов в множестве размер грамматки может получиться экспоненциальным.

Пример грамматики для которой имеет значение порядок нетерминалов

<tex>A_1 \to 0 | 1</tex>

<tex>A_{i+1} \to {A_i}0</tex> для <tex>1 \leq i < n</tex>

Упорядочим множество нетерминалов по возрастанию индексов. Легко заметить, что правила для <tex>A_i</tex> будут представлять из себя все двоичные вектора длины <tex>i</tex>, а значит размер грамматики будет экспоненциальным. Если упорядочить нетерминалы по убыванию в грамматике изменений не будет.

==Пример==
Дана грамматика

<tex>A \to S\alpha </tex>

<tex>S \to S\beta | A\gamma | b</tex>

Среди правил <tex>A</tex> непосредственной рекурсии нет, поэтому во время первой итерации внешнего цикла ничего не происходит.
Во время второй итерации внешнего цикла правило <tex> S \to A\gamma </tex> переходит в <tex> S \to S\alpha\gamma </tex>.

Грамматика имеет вид

<tex>A \to S\alpha </tex>

<tex>S \to{S}{\beta} | {S}{\alpha}{\gamma} | \beta</tex>

Устраняем левую рекурсию для <tex>S</tex>

<tex> S \to\beta{S_1}</tex>

<tex> {S_1} \to\beta{S_1} | \alpha\gamma{S_1}</tex>

==Литература==
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' — '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)
* ''Robert C. Moore'' — [http://aclweb.org/anthology-new/A/A00/A00-2033.pdf Removing Left Recursion from Context-Free Grammars ]

[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]

Устранение левой рекурсии

2013-01-18T18:25:00Z

94.25.229.56: /* Пример */

{{Определение
|definition=Говорят, что [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная (КС) грамматика]] <tex>\Gamma</tex> содержит '''непосредственную левую рекурсию''' (direct left recursion), если она содержит правило вида <tex>A \to A\alpha</tex>.
}}
{{Определение
|definition=Говорят, что КС-грамматика <tex>\Gamma</tex> содержит '''левую рекурсию (left recursion)''', если в ней существует вывод вида <tex>A \Rightarrow^* A\alpha</tex>.
}}

Методы нисходящего разбора (top-down parsers) не в состоянии работать с леворекурсивными грамматиками. Проблема в том, что продукция вида <tex>A \Rightarrow^* A\alpha</tex> может применяться бесконечно долго, так и не выработав некий терминальный символ, который можно было бы сравнить со строкой. Поэтому требуется преобразование грамматики, которое бы устранило левую рекурсию.

==Устранение непосредственной левой рекурсии==
Опишем процедуру, устраняющую все правила вида <tex>A \to A\alpha</tex>, для фиксированного нетерминала <tex>A</tex>.

<ol>
<li>Запишем все правила вывода из <tex>A</tex> в виде:
<tex>A \to A\alpha_1\,|\,\ldots\,|\,A\alpha_n\,|\,\beta_1\,|\,\ldots\,|\,\beta_m </tex>, где
<ul>
<li> <tex>\alpha</tex> {{---}} непустая последовательность терминалов и нетерминалов (<tex>\alpha \nrightarrow \varepsilon </tex>);</li>
<li> <tex>\beta</tex> {{---}} непустая последовательность терминалов и нетерминалов, не начинающаяся с <tex>A</tex>.</li>
</ul>
<li>Заменим правила вывода из <tex>A</tex> на <tex>A \to\beta_1A^\prime\, |\, \ldots\, |\, \beta_mA^\prime \,|\, \beta_1 \,|\, \ldots \,|\, \beta_m</tex>.</li>

<li>Создадим новый нетерминал <tex>{A^\prime} \to \alpha_1{A^\prime}, |\, \ldots\, |\, \alpha_n{A^\prime} | \alpha_1\, |\, \ldots\, |\, \alpha_n</tex>. </li>
</li>
</ol>

Изначально нетерминал <tex>A</tex> порождает сроки вида <tex>\beta\alpha_{i0}\alpha_{i1} \ldots \alpha_{ik}</tex>. В новой грамматике нетерминал <tex>A</tex> порождает <tex>\beta{A^\prime}</tex>, а <tex>A^\prime</tex> порождает строки вида <tex>\alpha_{i0}\alpha_{i1} \ldots \alpha_{ik}</tex>. Из этого очевидно, что изначальная грамматика эквивалентна новой.

===Пример===
<tex>A \to S\alpha | A\alpha</tex>

<tex>S \to A\beta</tex>

Есть непосредственная левая рекурсия <tex>A \to A\alpha</tex>. Добавим нетерминал <tex>A^\prime</tex> и добавим правила <tex>A \to S\alpha{A^{\prime}}</tex>, <tex> A^{\prime} \to \alpha{A^{\prime}} </tex>.

Новая грамматика:

<tex>A \to S\alpha{A^{\prime}} | S\alpha</tex>

<tex>A^{\prime} \to \alpha{A^{\prime}}</tex>

<tex>S \to A\beta</tex>

В новой грамматике нет непосредственной левой рекурсии, но нетерминал <tex>A</tex> леворекурсивен, так как есть <tex> A \Rightarrow S\alpha{A^{\prime}} \Rightarrow A\beta\alpha{A^{\prime}} </tex>

==Алгоритм устранения произвольной левой рекурсии==
Воспользуемся [[Удаление_eps-правил_из_грамматики | алгоритмом удаления <tex> \varepsilon </tex>-правил]]. Получим грамматику без <tex> \varepsilon </tex>-правил для языка <tex>L(\Gamma) \setminus \lbrace \epsilon \rbrace</tex>.

Упорядочим нетерминалы и будим добиваться того, чтобы не было правил вида <tex>A_i \to A_j\alpha</tex>, где <tex>j < i</tex>.
Можно заметить, что если данное условие выполняется для <tex>A_i</tex>, то в грамматике не будет <tex>A_i \Rightarrow^* A_i</tex>, а значит надо будет только устранить непосредственную левую рекурсию для <tex>A_i</tex>.

Пусть <tex>N = \lbrace A_1, A_2, \ldots , A_n \rbrace</tex> {{---}} упорядоченное множество всех нетерминалов.
<div>
for все нетерминалы <tex>A_i</tex>
for все нетерминалы <tex>A_j</tex>, такие, что <tex> 1 \leq j < i </tex> и
рассмотреть все правила вывода из <tex>A_j</tex>: <tex>A_j \to \delta_1 | \ldots | \delta_k</tex>.
заменить каждое правило <tex>A_i \to A_j \gamma</tex> на <tex>A_i \to \delta_1\gamma | \ldots | \delta_k\gamma</tex>.
устранить непосредственную левую рекурсию для <tex>A_i</tex>.
</div>

Если <tex>\varepsilon</tex> присутствовал в языке исходной грамматики, добавим новый начальный символ <tex>S'</tex> и правила <tex>S' \to S \, | \, \varepsilon </tex>.

На <tex>i</tex> итерации внешнего цикла все правила вида <tex>A_i \to A_j \gamma</tex> где <tex> j < i </tex> заменяются на <tex>A_i \to \delta_1\gamma | \ldots | \delta_k\gamma</tex> где <tex>A_j \to \delta_1 | \ldots | \delta_k</tex>. Таким образом остается только избавиться от непосредственной рекурсии для <tex>A_i</tex>.
Очевидно, что одна итерация алгоритма не меняет язык, а значит язык получившийся в итоге грамматики совпадает с исходным.

===Асимптотика===
Пусть <tex>a_i</tex> количество правил для нетерминала <tex>A_i</tex>.
Тогда <tex>i</tex> итерация внешнего цикла будет выполняться за <tex>O(\sum\limits_{A_i \to A_j, j < i} a_j) + O(a_i)</tex>, что меньше чем <tex>O(\sum\limits_{i=1}^n a_j)</tex>, значит асимптотика алгоритма <tex>O(n\sum\limits_{i=1}^n a_j)</tex>.

Проблема этого алгоритма в том, что в зависимости от порядка нетерминалов в множестве размер грамматки может получиться экспоненциальным.

Пример грамматики для которой имеет значение порядок нетерминалов

<tex>A_1 \to 0 | 1</tex>

<tex>A_{i+1} \to {A_i}0</tex> для <tex>1 \leq i < n</tex>

Упорядочим множество нетерминалов по возрастанию индексов. Легко заметить, что правила для <tex>A_i</tex> будут представлять из себя все двоичные вектора длины <tex>i</tex>, а значит размер грамматики будет экспоненциальным. Если упорядочить нетерминалы по убыванию в грамматике изменений не будет.

==Пример==
Дана грамматика

<tex>A \to S\alpha </tex>

<tex>S \to S\beta | A\gamma | b</tex>

Среди правил <tex>A</tex> непосредственной рекурсии нет, поэтому во время первой итерации внешнего цикла ничего не происходит.
Во время второй итерации внешнего цикла правило <tex> S \to A\gamma </tex> переходит в <tex> S \to S\alpha\gamma </tex>.

Грамматика имеет вид

<tex>A \to S\alpha </tex>

<tex>S \to{S}{\beta} | {S}{\alpha}{\gamma} | \beta</tex>

Устраняем левую рекурсию для <tex>S</tex>

<tex> S \to\beta{S_1}</tex>

<tex> {S_1} \to\beta{S_1} | \alpha\gamma{S_1}</tex>

==Литература==
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' — '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)
* ''Robert C. Moore'' — [http://aclweb.org/anthology-new/A/A00/A00-2033.pdf Removing Left Recursion from Context-Free Grammars ]

[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]

Устранение левой рекурсии

2013-01-18T18:23:46Z

94.25.229.56: /* Алгоритм устранения произвольной левой рекурсии */

{{Определение
|definition=Говорят, что [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная (КС) грамматика]] <tex>\Gamma</tex> содержит '''непосредственную левую рекурсию''' (direct left recursion), если она содержит правило вида <tex>A \to A\alpha</tex>.
}}
{{Определение
|definition=Говорят, что КС-грамматика <tex>\Gamma</tex> содержит '''левую рекурсию (left recursion)''', если в ней существует вывод вида <tex>A \Rightarrow^* A\alpha</tex>.
}}

Методы нисходящего разбора (top-down parsers) не в состоянии работать с леворекурсивными грамматиками. Проблема в том, что продукция вида <tex>A \Rightarrow^* A\alpha</tex> может применяться бесконечно долго, так и не выработав некий терминальный символ, который можно было бы сравнить со строкой. Поэтому требуется преобразование грамматики, которое бы устранило левую рекурсию.

==Устранение непосредственной левой рекурсии==
Опишем процедуру, устраняющую все правила вида <tex>A \to A\alpha</tex>, для фиксированного нетерминала <tex>A</tex>.

<ol>
<li>Запишем все правила вывода из <tex>A</tex> в виде:
<tex>A \to A\alpha_1\,|\,\ldots\,|\,A\alpha_n\,|\,\beta_1\,|\,\ldots\,|\,\beta_m </tex>, где
<ul>
<li> <tex>\alpha</tex> {{---}} непустая последовательность терминалов и нетерминалов (<tex>\alpha \nrightarrow \varepsilon </tex>);</li>
<li> <tex>\beta</tex> {{---}} непустая последовательность терминалов и нетерминалов, не начинающаяся с <tex>A</tex>.</li>
</ul>
<li>Заменим правила вывода из <tex>A</tex> на <tex>A \to\beta_1A^\prime\, |\, \ldots\, |\, \beta_mA^\prime \,|\, \beta_1 \,|\, \ldots \,|\, \beta_m</tex>.</li>

<li>Создадим новый нетерминал <tex>{A^\prime} \to \alpha_1{A^\prime}, |\, \ldots\, |\, \alpha_n{A^\prime} | \alpha_1\, |\, \ldots\, |\, \alpha_n</tex>. </li>
</li>
</ol>

Изначально нетерминал <tex>A</tex> порождает сроки вида <tex>\beta\alpha_{i0}\alpha_{i1} \ldots \alpha_{ik}</tex>. В новой грамматике нетерминал <tex>A</tex> порождает <tex>\beta{A^\prime}</tex>, а <tex>A^\prime</tex> порождает строки вида <tex>\alpha_{i0}\alpha_{i1} \ldots \alpha_{ik}</tex>. Из этого очевидно, что изначальная грамматика эквивалентна новой.

===Пример===
<tex>A \to S\alpha | A\alpha</tex>

<tex>S \to A\beta</tex>

Есть непосредственная левая рекурсия <tex>A \to A\alpha</tex>. Добавим нетерминал <tex>A^prime</tex> и добавим правила <tex>A \to S\alpha{A^{\prime}}</tex>, <tex> A^{\prime} \to \alpha{A^{\prime}} </tex>.

Новая грамматика:

<tex>A \to S\alpha{A^{\prime}} | S\alpha</tex>

<tex>A^{\prime} \to \alpha{A^{\prime}}</tex>

<tex>S \to A\beta</tex>

В новой грамматике нет непосредственной левой рекурсии, но нетерминал <tex>A</tex> леворекурсивен, так как есть <tex> A \Rightarrow S\alpha{A^{\prime}} \Rightarrow A\beta\alpha{A^{\prime}} </tex>

==Алгоритм устранения произвольной левой рекурсии==
Воспользуемся [[Удаление_eps-правил_из_грамматики | алгоритмом удаления <tex> \varepsilon </tex>-правил]]. Получим грамматику без <tex> \varepsilon </tex>-правил для языка <tex>L(\Gamma) \setminus \lbrace \epsilon \rbrace</tex>.

Упорядочим нетерминалы и будим добиваться того, чтобы не было правил вида <tex>A_i \to A_j\alpha</tex>, где <tex>j < i</tex>.
Можно заметить, что если данное условие выполняется для <tex>A_i</tex>, то в грамматике не будет <tex>A_i \Rightarrow^* A_i</tex>, а значит надо будет только устранить непосредственную левую рекурсию для <tex>A_i</tex>.

Пусть <tex>N = \lbrace A_1, A_2, \ldots , A_n \rbrace</tex> {{---}} упорядоченное множество всех нетерминалов.
<div>
for все нетерминалы <tex>A_i</tex>
for все нетерминалы <tex>A_j</tex>, такие, что <tex> 1 \leq j < i </tex> и
рассмотреть все правила вывода из <tex>A_j</tex>: <tex>A_j \to \delta_1 | \ldots | \delta_k</tex>.
заменить каждое правило <tex>A_i \to A_j \gamma</tex> на <tex>A_i \to \delta_1\gamma | \ldots | \delta_k\gamma</tex>.
устранить непосредственную левую рекурсию для <tex>A_i</tex>.
</div>

Если <tex>\varepsilon</tex> присутствовал в языке исходной грамматики, добавим новый начальный символ <tex>S'</tex> и правила <tex>S' \to S \, | \, \varepsilon </tex>.

На <tex>i</tex> итерации внешнего цикла все правила вида <tex>A_i \to A_j \gamma</tex> где <tex> j < i </tex> заменяются на <tex>A_i \to \delta_1\gamma | \ldots | \delta_k\gamma</tex> где <tex>A_j \to \delta_1 | \ldots | \delta_k</tex>. Таким образом остается только избавиться от непосредственной рекурсии для <tex>A_i</tex>.
Очевидно, что одна итерация алгоритма не меняет язык, а значит язык получившийся в итоге грамматики совпадает с исходным.

===Асимптотика===
Пусть <tex>a_i</tex> количество правил для нетерминала <tex>A_i</tex>.
Тогда <tex>i</tex> итерация внешнего цикла будет выполняться за <tex>O(\sum\limits_{A_i \to A_j, j < i} a_j) + O(a_i)</tex>, что меньше чем <tex>O(\sum\limits_{i=1}^n a_j)</tex>, значит асимптотика алгоритма <tex>O(n\sum\limits_{i=1}^n a_j)</tex>.

Проблема этого алгоритма в том, что в зависимости от порядка нетерминалов в множестве размер грамматки может получиться экспоненциальным.

Пример грамматики для которой имеет значение порядок нетерминалов

<tex>A_1 \to 0 | 1</tex>

<tex>A_{i+1} \to {A_i}0</tex> для <tex>1 \leq i < n</tex>

Упорядочим множество нетерминалов по возрастанию индексов. Легко заметить, что правила для <tex>A_i</tex> будут представлять из себя все двоичные вектора длины <tex>i</tex>, а значит размер грамматики будет экспоненциальным. Если упорядочить нетерминалы по убыванию в грамматике изменений не будет.

==Пример==
Дана грамматика

<tex>A \to S\alpha </tex>

<tex>S \to S\beta | A\gamma | b</tex>

Среди правил <tex>A</tex> непосредственной рекурсии нет, поэтому во время первой итерации внешнего цикла ничего не происходит.
Во время второй итерации внешнего цикла правило <tex> S \to A\gamma </tex> переходит в <tex> S \to S\alpha\gamma </tex>.

Грамматика имеет вид

<tex>A \to S\alpha </tex>

<tex>S \to{S}{\beta} | {S}{\alpha}{\gamma} | \beta</tex>

Устраняем левую рекурсию для <tex>S</tex>

<tex> S \to\beta{S_1}</tex>

<tex> {S_1} \to\beta{S_1} | \alpha\gamma{S_1}</tex>

==Литература==
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' — '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)
* ''Robert C. Moore'' — [http://aclweb.org/anthology-new/A/A00/A00-2033.pdf Removing Left Recursion from Context-Free Grammars ]

[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]