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


Расширенный магазинный автомат - часть 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}.  
       

 

 

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




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