Расширенный магазинный автомат - часть 2

При этом начальная и конечная конфигурации имеют вид:

(s0, a,р

h0 ) и (s1, $, h0I ),

где a - заданная цепочка, s1 - одно из заключительных состояний автомата, I - начальная аксиома грамматики.
Цепочку и язык, допускаемые расширенным автоматом, можно определить так.

Определение.

                     Цепочка допускается расширенным автоматом, если
                     существует последовательность конфигураций,
                      первая из которых является начальной конфигурацией
                       с заданной цепочкой, а последней конфигурацией в
                        последовательности является одна из
                         заключительных конфигураций.

                              ( s0, a,р h0

) , $|--* ( s1, h0I ),

где s1 - одно из заключительных состояний,

a - заданная цепочка.

Определение.

Язык, допускаемый расширенным автоматом, можно
определить так:

L(M) = { a | (s0, a,р h0 ) |--* ( s1, $,$ ) и s1ОF}.

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

Начало Назад Вперед