Расширенный магазинный автомат
Рассмотренный пример показывает, что автомат, выполняющий операцию свертки, в отличие от нисходящего распознавателя, не строит в магазине вывод цепочки, начиная с аксиомы грамматики, который соответствует построению синтаксического дерева цепочки "сверху - вниз", а выполняет сворачивание символов, записанных в магазин. Такой порядок сворачивания символов, записанных в магазин, соответствует правому выводу цепочки, выполняемому "снизу - вверх". Это обстоятельство объясняет, почему такие распознаватели называются восходящими. Подобный распознаватель должен учитывать при переходе не один символ, расположенный в вершине магазина, а цепочку символов. Чтобы устранить отмеченное противоречие, определим новый тип автомата, который назовем расширенным магазиннным автоматом.
| Определение. Формальное определение такого автомата имеет вид: M = {P, S, H, F, s0, h0, d}, где {$}} * 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 - заданная цепочка. Определение. Язык, допускаемый расширенным автоматом, можно определить так:
|
