170
правок
Изменения
Нет описания правки
|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>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>определена следующим образом:
