Изменения

Перейти к: навигация, поиск
Нет описания правки
|id = th1
|statement = Класс контекстно-свободных языков (<tex>\mathrm{CFG}</tex>) является подмножеством класса языков, задаваемых автоматами с магазинной памятью (<tex>\mathrm{PDA}</tex>), то есть по любой КС-грамматике можно построить МП-автомат, задающий тот же язык, что и исходная грамматика.
|proof = <!-- Пусть <tex> G=(V,T,Q,S) </tex> — КС-грамматика. Построим МП-автомат <tex> P=(\{q\},T,V \cup T, \delta ,q,S) </tex>, который допускает <tex> L(G) </tex> по пустому магазину. Функция переходов <tex> \delta </tex> будет определена по следующим правилам:*1. <tex> \delta(q,\varepsilon,A)=\{(q,\beta )| A \rightarrow \beta</tex> — продукция <tex> G \} </tex> для каждой переменной <tex> A </tex>. *2. <tex> \delta(q,a,a)=\{(q,\varepsilon)\} </tex> для каждого терминала <tex> a </tex>.-->
Пусть дана КС-грамматика <tex>\Gamma =\langle \Sigma, N, S, P\rangle</tex>. Поскольку классы языков, допускаемых МП-автоматами по допускающему состоянию и по пустому стеку, [[МП-автоматы, допуск по пустому стеку и по допускающему состоянию, эквивалентность | совпадают]], достаточно построить автомат с допуском по пустому стеку.
Построим автомат из одного состояния <tex>q</tex> с входным алфавитом <tex>\Sigma</tex>, стековым алфавитом <tex>N \cup \Sigma</tex>, маркером дна <tex>S</tex> и функцией перехода <tex>\delta</tex>, определённой ниже. Формально <tex>A = \langle \Sigma, N \cup \Sigma, \{q\}, q, S, \delta \rangle</tex>, где <tex>\delta</tex> задаётся следующим образом:
 
[[Файл:Delta.png | thumb | right | Добавим такие переходы для каждого терминала <tex>a</tex> и правила вывода <tex>V \rightarrow \gamma</tex>]]
1) для каждого правила вывода <tex>V \rightarrow \gamma \in P</tex> определим <tex>\delta(q, \varepsilon, V) = \{(q, \gamma)\}</tex>;
2) для каждого терминала <tex>a</tex> определим <tex> \delta(q, a, a) = \{(q, \varepsilon)\} </tex>.
<!--
Пусть <tex> w\in L(G)</tex>, тогда <tex> w </tex> имеет следующее левое порождение:
<tex> S = \gamma_1 \Rightarrow \gamma_2 \Rightarrow ... \Rightarrow \gamma_n=w</tex>.
Покажем индукцией по <tex> i </tex>, что <tex> (q,w,S)\vdash^*(q,y_i,\alpha_i)</tex>:
*База. Очевидно, что <tex> (q,w,S)\vdash^*(q,w,S) </tex>.
*Переход. Предположим, что <tex> (q,w,S)\vdash^*(q,w_i,\alpha_i) </tex>. Заметим, что шаг порождения <tex> y_i \Rightarrow y_{i+1}</tex> включает замену некоторой переменной <tex> A </tex> ее продукцией <tex> \beta </tex>. Правило 1 построения МП-автомата позволяет на заменить <tex> A </tex> на вершине стека на цепочку <tex> \beta </tex>, а правило 2 позволяет затем сравнить любые терминалы на вершине со входными символами. В результате достигается МО <tex> (q,y_{i+1},\alpha_{i+1}) </tex>.
*Также заметим, что <tex> \alpha_n = \varepsilon</tex>. Таким образом <tex> (q,w,S)\vdash^*(q,\varepsilon,\varepsilon) </tex>, т.е допускает <tex> P </tex> по пустому стеку.
-->
Покажем, что язык, допускаемый автоматом <tex>A</tex>, совпадает с языком грамматики <tex>\Gamma</tex>, то есть что <tex>S \Rightarrow^* w \iff (q, w, S) \vdash^* (q, \varepsilon, \varepsilon)</tex>:
==== Пример ====
Преобразуем КС-грамматику выражений слов над алфавитом <tex>\{0, 1\}</tex>, в которых поровну нулей и единиц, в МП-автомат. Пусть дана грамматика:*<tex> I S \rightarrow a|b|I1|I0|Ia|Ib 0S1 </tex>,;*<tex> E S \rightarrow I|E1S0 </tex>;*E|E+E|(E) <tex> S \rightarrow \varepsilon </tex>.Множеством входных символов терминалов является <tex> \Sigma = \{a,b0,1\}</tex>,0,(,),+,*а нетерминалов {{---}} <tex>N = \{S\} </tex>. Эти символы вместе с переменными Таким образом, стековый алфавит состоит из <tex> I0, 1,E S</tex> образуют магазинный алфавит. Функция переходов определена следующим образом: a) <tex> \delta(q,\varepsilon,I)={(q,a), (q,b), (q,Ia), (q,Ib), (q,I0), (q,I1)};</tex>определена следующим образом:
ba) <tex> \delta(q,\varepsilon,ES)=\{(q,I0S1), (q,E+E1S0), (q,E*E\varepsilon), \}</tex> (q,(E))};в соответствии с первым пунктом построения <tex>\delta</tex>);
cb) <tex> \delta(q, a0, a0) = \{(q, \varepsilon)\}</tex>; <tex> \delta(q, b1, b1) = \{(q, \varepsilon)\}</tex>; (в соответствии со вторым пунктом построения <tex> \delta(q, 0, 0) = \{(q, \varepsilon)\}</tex>; <tex> \delta(q, 1, 1) = \{(q, \varepsilon)\}</tex>.
Пункты '''a,b''' образованы по первому правилу построения функции переходов, а пункт '''c''' по второмуПолучившийся автомат:[[Файл:Example1.png]]
170
правок

Навигация