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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Праволинейной грамматикой''' <tex>\Gamma</tex> называется грамматика, в которой все правила имеют вид
+
'''Праволинейной грамматикой''' <tex>\Gamma</tex> называется грамматика, в которой все правила имеют вид <tex> A \to a </tex>, <tex> A \to aB </tex>.
 +
}}
 +
 
 +
Аналогично можно определить леволинейные грамматики.
 +
 
 +
{{Теорема
 +
|statement=
 +
Множество языков, задаваемых праволинейными грамматиками совпадает со множеством языков, задаваемых конечными автоматами.
 +
|proof=
 +
Пусть имеется конечный автомат. Построим для него праволинейную грамматику. Множеством нетерминалов нашей грамматики будет множество состояний автомата. Для каждой пары состояний автомата <tex>A</tex> и <tex>B</tex> таких, что имеется переход из <tex>A</tex> в <tex>B</tex>  по символу <tex>c</tex>, и <tex> B </tex> – не является допускающим состоянием в автомате, добавим в грамматику правило <tex> A \to cB </tex>. Затем для каждой пары состояний автомата <tex>A</tex> и <tex>B</tex> таких, что имеется переход из <tex>A</tex> в <tex>B</tex>  по символу <tex>c</tex>, и <tex> B </tex> – является допускающим состоянием в автомате, добавим в грамматику правило <tex> A \to c </tex>.
 +
 
 +
Докажем, что если для автомата верно <tex>\langle S, \alpha \rangle \vdash^* \langle U, \varepsilon \rangle </tex>, то для построенной грамматики верно <tex> S \Rightarrow^* \alpha U </tex>. Будем доказывать индукцией по переходам в автомате.
 +
 
 +
Базой индукции будут переходы за 0 шагов.
 +
Индукционный переход: пусть данное свойство выполняется для переходов длины <tex>k-1</tex>. Докажем что верно и для переходов за <tex>k</tex> шагов.
 +
 
 +
Рассмотрим переход <tex>\langle S, \alpha \rangle \vdash^{k} \langle U, \varepsilon \rangle </tex>, а именно его последний шаг: <tex> \langle S, \alpha \rangle \vdash^{k-1} \langle Q, c \rangle \vdash \langle U, \varepsilon \rangle </tex>
 +
Так как для <tex>k-1</tex> шагов верно, то <tex> S \Rightarrow^{k-1} \alpha c^{-1} Q </tex> но по построению грамматики имеется правило <tex> Q \to c U</tex>, значит <tex> S \Rightarrow^{k-1} \alpha c^{-1} Q  \Rightarrow \alpha c^{-1} c U = \alpha U</tex>. Таким образом доказали для <tex>k</tex> шагов.
 +
 
 +
Теперь пусть имеется праволинейная грамматика. Построим по ней конечный детерминированный автомат.
 +
Введем специальное допускающее состояние <tex> ok </tex>. Множеством состояний автомата будет множество нетерминалов грамматики вместе с состоянием <tex> ok </tex> (<tex> Q = N \cup ok </tex>). Для правил вида <tex> A \to aB </tex> определим функцию перехода в автомате как <tex> \delta \left( A, a \right) = B </tex>. Для правил вида <tex> A \to a </tex>  определим функцию перехода в автомате как <tex> \delta \left( A, a \right) = ok </tex>
 +
 
 +
 
 
}}
 
}}

Версия 06:02, 12 октября 2010

Определение:
Праволинейной грамматикой [math]\Gamma[/math] называется грамматика, в которой все правила имеют вид [math] A \to a [/math], [math] A \to aB [/math].


Аналогично можно определить леволинейные грамматики.

Теорема:
Множество языков, задаваемых праволинейными грамматиками совпадает со множеством языков, задаваемых конечными автоматами.
Доказательство:
[math]\triangleright[/math]

Пусть имеется конечный автомат. Построим для него праволинейную грамматику. Множеством нетерминалов нашей грамматики будет множество состояний автомата. Для каждой пары состояний автомата [math]A[/math] и [math]B[/math] таких, что имеется переход из [math]A[/math] в [math]B[/math] по символу [math]c[/math], и [math] B [/math] – не является допускающим состоянием в автомате, добавим в грамматику правило [math] A \to cB [/math]. Затем для каждой пары состояний автомата [math]A[/math] и [math]B[/math] таких, что имеется переход из [math]A[/math] в [math]B[/math] по символу [math]c[/math], и [math] B [/math] – является допускающим состоянием в автомате, добавим в грамматику правило [math] A \to c [/math].

Докажем, что если для автомата верно [math]\langle S, \alpha \rangle \vdash^* \langle U, \varepsilon \rangle [/math], то для построенной грамматики верно [math] S \Rightarrow^* \alpha U [/math]. Будем доказывать индукцией по переходам в автомате.

Базой индукции будут переходы за 0 шагов. Индукционный переход: пусть данное свойство выполняется для переходов длины [math]k-1[/math]. Докажем что верно и для переходов за [math]k[/math] шагов.

Рассмотрим переход [math]\langle S, \alpha \rangle \vdash^{k} \langle U, \varepsilon \rangle [/math], а именно его последний шаг: [math] \langle S, \alpha \rangle \vdash^{k-1} \langle Q, c \rangle \vdash \langle U, \varepsilon \rangle [/math] Так как для [math]k-1[/math] шагов верно, то [math] S \Rightarrow^{k-1} \alpha c^{-1} Q [/math] но по построению грамматики имеется правило [math] Q \to c U[/math], значит [math] S \Rightarrow^{k-1} \alpha c^{-1} Q \Rightarrow \alpha c^{-1} c U = \alpha U[/math]. Таким образом доказали для [math]k[/math] шагов.

Теперь пусть имеется праволинейная грамматика. Построим по ней конечный детерминированный автомат.

Введем специальное допускающее состояние [math] ok [/math]. Множеством состояний автомата будет множество нетерминалов грамматики вместе с состоянием [math] ok [/math] ([math] Q = N \cup ok [/math]). Для правил вида [math] A \to aB [/math] определим функцию перехода в автомате как [math] \delta \left( A, a \right) = B [/math]. Для правил вида [math] A \to a [/math] определим функцию перехода в автомате как [math] \delta \left( A, a \right) = ok [/math]
[math]\triangleleft[/math]