Составители:
69
Глава 5
МАГАЗИННЫЕ АВТОМАТЫ
§ 5.1. Неформальное описание
В этой главе мы рассмотрим простое устройство — магазинный автомат
7
(pda —
pushdown automaton), которое адекватно классу КС-языков в том
смысле, что любой КС-язык распознаётся каким-нибудь магазинным
автоматом, и любой магазинный автомат распознаёт некоторый КС-язык.
Магазинный автомат подобен конечному автомату, но в отличие от последнего
имеет рабочую память — магазин, в который записываются символы из ещё
одного алфавита — алфавита магазинных символов. Каждое движение
магазинного
автомата определяется в зависимости от текущего состояния
управления, входного символа или независимо от него — так называемые ε-
движения и от верхнего символа магазина. Одно движение магазинного
автомата
состоит в замещении верхнего символа магазина некоторой
магазинной цепочкой, в частности пустой (стирание верхнего символа
магазина), и переходе в новое состояние управления. При этом текущим
входным символом становится следующий символ на входной ленте, если
выполняется движение, зависящее от входного символа, либо текущий входной
символ остаётся тем же самым, если выполняется ε-движение. Поскольку
движение зависит от верхнего символа магазина, то с самого начала в магазине
находится один символ — начальный символ магазина.
Считается, что некоторая цепочка принята, если магазинный автомат из
начального состояния управления, имея в магазине единственный —
начальный символ магазина и прочитав данную цепочку на входе, переходит в
одно из своих конечных состояний или опустошает магазин. Каждый
конкретный магазинный автомат использует только какой-нибудь один из этих
двух признаков приёма входной цепочки. Как и в случае конечных автоматов
существуют
две модели магазинных автоматов — недетерминированная и
детерминированная.
В недетерминированной модели автомат каждый раз имеет
возможность некоторого конечного выбора движений и совершает одно из них.
Входная цепочка считается принятой, если существует хотя бы одна
последовательность выборов движений, которая приводит автомат к конечной
конфигурации — входная цепочка прочитана, текущее состояние — конечное
или (в другом варианте) магазин пуст. В противном случае она не принимается.
Множество всех цепочек, принимаемых данным магазинным автоматом,
называется языком, распознаваемым этим магазинным автоматом.
В данной главе будет показано, что оба определения приёма эквивалентны
в том смысле, что если язык принимается некоторым магазинным автоматом
при пустом магазине, то он может быть принят некоторым другим магазинным
автоматом при конечном состоянии, и наоборот.
7
Вместо этого термина часто используется сокращение МП-автомат.
Страницы
- « первая
- ‹ предыдущая
- …
- 68
- 69
- 70
- 71
- 72
- …
- следующая ›
- последняя »
