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

       

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


Рассмотренный пример показывает, что автомат, выполняющий операцию свертки, в отличие от нисходящего распознавателя, не строит в магазине вывод цепочки, начиная с аксиомы грамматики, который соответствует построению синтаксического дерева цепочки "сверху - вниз", а выполняет  сворачивание символов, записанных в магазин. Такой порядок сворачивания символов, записанных в магазин, соответствует правому выводу цепочки, выполняемому "снизу - вверх". Это обстоятельство объясняет, почему такие распознаватели называются восходящими. Подобный распознаватель должен учитывать при переходе не один символ, расположенный в вершине магазина, а цепочку символов. Чтобы устранить отмеченное противоречие, определим новый тип автомата, который назовем расширенным магазиннным автоматом.


 
 

 Определение
                         Формальное определение такого автомата имеет вид: 

     M = {P, S, H, F, s0, h0, d},

 где  
    P - входной алфавит, 
    S - алфавит состояний, 
    s0- начальное состояние , s0 ОS, 
    F - множество конечных состояний, F является подмножеством S,  
    H - алфавит магазинных сисмволов, записываемых на вспомогательную ленту,  
    h0 - маркер дна, он всегда записывается на дно магазина, h0 О  H, 
    d: S * {P И

{$}} * H* ®

S*H* - функция переходов. 
 

В функциональном виде функции переходов расширенного автомата можно записать так:      d(s, p, ga) = (s, gb),

где a, b, g О



H*, p О (P И

{$}) и s О S.
Приведенное определение показывает, что расширенный автомат допускает замену одной цепочки, находящейся в вершине автомата, другой цепочкой.
Используя введенное  ранее определение конфигурации  автомата, работу расширенного  магазинного автомата можно представить в виде последовательности сменяющих друг друга конфигураций.
При этом начальная и конечная конфигурации имеют вид:

(s0, a,р

h0 ) и (s1, $, h0I ),

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

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

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

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

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

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

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

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


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


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


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