175
правок
Изменения
→Построение МП-автомата по заданной КС-грамматике
=== Построение МП-автомата по заданной КС-грамматике ===
{{Определение
|definition= Пусть <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,\epsilon,A)=\{(q,\beta )| A \rightarrow \beta</tex> — продукция <tex> G \} </tex> — для каждой переменной <tex> A </tex>. * 2. <tex> \delta(q,a,a)=\{(q,\epsilon)\} </tex> для каждого терминала <tex> a </tex>.
}}
==== Пример. ====
*b) <tex> \delta(q,\epsilon,E)={(q,I), (q,E+E), (q,E*E), (q,(E))};</tex>
*c) <tex> \delta(q,a,a)=\{(q,\epsilon)\}</tex>;<tex> \delta(q,b,b)=\{(q,\epsilon)\}</tex>;<tex> \delta(q,1,1)=\{(q,\epsilon)\}</tex>;<tex> \delta(q,0,0)=\{(q,\epsilon)\}</tex>;<tex> \delta(q,),))=\{(q,\epsilon)\}</tex>;<tex> \delta(q,(,()=\{(q,\epsilon)\}</tex>;<tex> \delta(q,+,+)=\{(q,\epsilon)\}</tex>;<tex> \delta(q,*,*)=\{(q,\epsilon)\}</tex>;
Пункты a,b образованы по первому правилу построения функции переходов, пункт c по второму правилу.
