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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Финальная версия)
м
Строка 30: Строка 30:
 
Введем специальное допускающее состояние <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>.
 
Введем специальное допускающее состояние <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>.
  
Докажем, что если слово выводится в грамматике, то оно допускается автоматом. Рассмотрим последовательность применений правил, дающую слово <tex> \alpha </tex> длины <tex> k </tex>. Для каждого правила вида <tex> A \to aB </tex> в автомате существует переход из состояния <tex> A </tex> в состояние <tex> B</tex> по символу <tex> a </tex>. Таким образом, если после <tex> k-1 </tex> применения правил мы можем получить строку вида <tex> \alpha c^{-1}B </tex>, то в автомате имеется последовательность переходов <tex> \langle S, \alpha  \rangle \vdash^{k-1} \langle B, c \rangle </tex>, а поскольку можно вывести <tex> \alpha </tex>, то хотя бы для одной строки такого вида существует правило <tex> B \to c </tex>, а значит в автомате есть переход <tex> \langle B,c \rangle \vdash \langle ok,\varepsilon \rangle </tex>. Таким образом автомат допускает слово <tex> \alpha </tex>.
+
Докажем, что если слово выводится в грамматике, то оно допускается автоматом. Рассмотрим последовательность применений правил, дающую слово <tex> \alpha </tex> длины <tex> k </tex>. Для каждого правила вида <tex> A \to aB </tex> в автомате существует переход из состояния <tex> A </tex> в состояние <tex> B</tex> по символу <tex> a </tex>. Таким образом, если после <tex> k-1 </tex> применения правил мы можем получить строку вида <tex> \alpha c^{-1}B </tex>, то в автомате имеется соответствующая последовательность переходов <tex> \langle S, \alpha  \rangle \vdash^{k-1} \langle B, c \rangle </tex>, а поскольку можно вывести <tex> \alpha </tex>, то хотя бы для одной строки такого вида существует правило <tex> B \to c </tex>, а значит в автомате есть переход <tex> \langle B,c \rangle \vdash \langle ok,\varepsilon \rangle </tex>. Таким образом автомат допускает слово <tex> \alpha </tex>.
  
Докажем, что если слово допускается автоматом, то его можно вывести в грамматике. Рассмотрим слово <tex> \alpha </tex>  длины <tex> k </tex>. Рассмотрим какую-либо последовательность переходов автомата, допускающую данное слово <tex> \langle S,\alpha \rangle \vdash^k  \langle ok,\varepsilon \rangle </tex>. Для каждого одношагового перехода в автомате существует соответствующее правило в грамматике. Значит для подпоследовательности переходов из <tex> k-1 </tex> шага <tex> \langle S, \alpha \rangle \vdash^{k-1} \langle U,c \rangle </tex> существует последовательность применений правил <tex> S \Rightarrow^{k-1} \alpha c^{-1} U </tex>. Для последнего перехода в автомате <tex> \langle U,c \rangle \vdash \langle ok, \varepsilon \rangle </tex> существует правило <tex> U \Rightarrow c </tex>. Таким образом, существует последовательность применений правил грамматики, выводящая слово <tex> \alpha </tex>.
+
Докажем, что если слово допускается автоматом, то его можно вывести в грамматике. Рассмотрим слово <tex> \alpha </tex>  длины <tex> k </tex>. Рассмотрим какую-либо последовательность переходов автомата, допускающую данное слово <tex> \langle S,\alpha \rangle \vdash^k  \langle ok,\varepsilon \rangle </tex>. Для каждого одношагового перехода в автомате существует соответствующее правило в грамматике. Значит для подпоследовательности переходов из <tex> k-1 </tex> шага <tex> \langle S, \alpha \rangle \vdash^{k-1} \langle U,c \rangle </tex> существует соответствующая последовательность применений правил <tex> S \Rightarrow^{k-1} \alpha c^{-1} U </tex>. Для последнего перехода в автомате <tex> \langle U,c \rangle \vdash \langle ok, \varepsilon \rangle </tex> существует правило <tex> U \Rightarrow c </tex>. Таким образом, существует последовательность применений правил грамматики, выводящая слово <tex> \alpha </tex>.
  
 
Теорема доказана.
 
Теорема доказана.
  
 
}}
 
}}

Версия 04:35, 14 октября 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] 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] S \Rightarrow^* \alpha U [/math] следует [math] \langle S, \alpha \rangle \vdash^* \langle U, \varepsilon \rangle [/math]. Доказательство так же проведем по индукции. Индукция будет идти по количеству примененных подряд правил.

Базой индукции будут строки, выводимые в грамматике из начального нетерминала [math] S [/math] за 0 применений правил.

Индукционный переход: пусть верно для [math]k-1[/math] применения правил. Рассмотрим произвольную строку, полученную за [math]k[/math] применений правил. Рассмотрим последнее применение правила. Если оно имело вид [math] A \to aB [/math], значит в автомате возможен переход [math] \langle A,a \rangle \vdash \langle B,\varepsilon \rangle [/math], а если [math] A \to a [/math], то [math] B [/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] \alpha [/math] длины [math] k [/math]. Для каждого правила вида [math] A \to aB [/math] в автомате существует переход из состояния [math] A [/math] в состояние [math] B[/math] по символу [math] a [/math]. Таким образом, если после [math] k-1 [/math] применения правил мы можем получить строку вида [math] \alpha c^{-1}B [/math], то в автомате имеется соответствующая последовательность переходов [math] \langle S, \alpha \rangle \vdash^{k-1} \langle B, c \rangle [/math], а поскольку можно вывести [math] \alpha [/math], то хотя бы для одной строки такого вида существует правило [math] B \to c [/math], а значит в автомате есть переход [math] \langle B,c \rangle \vdash \langle ok,\varepsilon \rangle [/math]. Таким образом автомат допускает слово [math] \alpha [/math].

Докажем, что если слово допускается автоматом, то его можно вывести в грамматике. Рассмотрим слово [math] \alpha [/math] длины [math] k [/math]. Рассмотрим какую-либо последовательность переходов автомата, допускающую данное слово [math] \langle S,\alpha \rangle \vdash^k \langle ok,\varepsilon \rangle [/math]. Для каждого одношагового перехода в автомате существует соответствующее правило в грамматике. Значит для подпоследовательности переходов из [math] k-1 [/math] шага [math] \langle S, \alpha \rangle \vdash^{k-1} \langle U,c \rangle [/math] существует соответствующая последовательность применений правил [math] S \Rightarrow^{k-1} \alpha c^{-1} U [/math]. Для последнего перехода в автомате [math] \langle U,c \rangle \vdash \langle ok, \varepsilon \rangle [/math] существует правило [math] U \Rightarrow c [/math]. Таким образом, существует последовательность применений правил грамматики, выводящая слово [math] \alpha [/math].

Теорема доказана.
[math]\triangleleft[/math]