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


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


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


 
 

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

     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.
Приведенное определение показывает, что расширенный автомат допускает замену одной цепочки, находящейся в вершине автомата, другой цепочкой.
Используя введенное  ранее определение конфигурации  автомата, работу расширенного  магазинного автомата можно представить в виде последовательности сменяющих друг друга конфигураций.


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