Формальные языки

       

Построение множества ВЫБОР


Множество ВЫБОР, которое потребуется нам для построения переходов магазинных автоматов,можно определить  с помощью функций ПЕРВ и СЛЕД следующим образом: 1)   Если правило грамматики имеет вид <B>

- > a и

a не является аннулирующей цепочкой, другими словами не существует вывод a

==>*$, то
 

ВЫБОР(<B>  ®

a ) = ПЕРВ( a ).

 
2)    Для аннулирующих правил грамматики вида <B>  ®$, мно-
жество выбора определяется так
 

ВЫБОР(<B> 

® $) = СЛЕД(<B>).

 
3)    Если правило грамматики имеет вид <B>  ® µ и µ

яв-
ляется аннулирующей цепочкой, то

ВЫБОР(<B> 

® µ) = ПЕРВ(µ) И



СЛЕД(<B>).

Для рассматриваемой грамматики Г3.2 множества ВЫБОР для каждого из правил, построенные описанным выше способом, имеют вид:

ВЫБОР(<A>  ®

<B><C>c) = ПЕРВ(<B><C>c) = {a,b,c,d},
ВЫБОР(<A>  ®

g<D><B>) = ПЕРВ(g<D><B>) = {g},
ВЫБОР(<B>  ®

$) = ПЕРВ($) И

СЛЕД(<B>) = {a,c,d,g,f},
ВЫБОР(<B>  ®

b<C><D><E>) = ПЕРВ(b<C><D><E>) = {b},
ВЫБОР(<C>  ®

<D>a<B>) = ПЕРВ(<D>a<B>) = {a,d},
ВЫБОР(<C>  ®

ca) = ПЕРВ(ca) = {a},
ВЫБОР(<D>  ®

$) = ПЕРВ($) И

СЛЕД(<D>) = {a,b,c,g,f},
ВЫБОР(<D>  ®

d<D>) = ПЕРВ(d<D>) = {d},
ВЫБОР(<E>  ®

g<A>f) = ПЕРВ(g<A>f) = {g},
ВЫБОР(<E>  ®

c) = ПЕРВ(c) = {c}.

Пред.Страница 

След.Страница   Раздел   Содержание



Содержание раздела