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

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

Рассмотренный пример показывает, что автомат, выполняющий операцию свертки, в отличие от нисходящего распознавателя, не строит в магазине вывод цепочки, начиная с аксиомы грамматики, который соответствует построению синтаксического дерева цепочки "сверху - вниз", а выполняет  сворачивание символов, записанных в магазин. Такой порядок сворачивания символов, записанных в магазин, соответствует правому выводу цепочки, выполняемому "снизу - вверх". Это обстоятельство объясняет, почему такие распознаватели называются восходящими. Подобный распознаватель должен учитывать при переходе не один символ, расположенный в вершине магазина, а цепочку символов. Чтобы устранить отмеченное противоречие, определим новый тип автомата, который назовем расширенным магазиннным автоматом.
 
 
 Определение. 
                         Формальное определение такого автомата имеет вид:  
     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}.  
       
 
 
Пред.Страница  След.Страница  Раздел  Содержание  >