Теория и реализация языков программирования




Контекстно-свободные грамматики и автоматы с магазинной памятью - часть 2


Автомат с магазинной памятью (МП-автомат) - это семерка M = (Q, T, ?, D, q0, Z0, F), где

(1) Q - конечное множество состояний, представляющих всевозможные состояния управляющего устройства;

(2) T - конечный входной алфавит;

(3) ? - конечный алфавит магазинных символов;

(4) D - отображение множества Q x (T

{e}) x ? в множество конечных подмножеств Q x ?*, называемое функцией переходов;

(5)

q_0 \in Q
- начальное состояние управляющего устройства;

(6)

Z_0 \in \Gamma
- символ, находящийся в магазине в начальный момент (начальный символ магазина);

(7)

F \subseteq Q
- множество заключительных состояний.

Конфигурация МП-автомата - это тройка (q, w, u), где

(1)

q \in Q
- текущее состояние управляющего устройства;

(2)

w \in T^*
- непрочитанная часть входной цепочки; первый символ цепочки w находится под входной головкой; если w = e, то считается, что вся входная лента прочитана;

(3)

u \in \Gamma^*
- содержимое магазина; самый левый символ цепочки u считается верхним символом магазина; если u = e, то магазин считается пустым.

Такт работы МП-автомата M будем представлять в виде бинарного отношения

\vdash
, определенного на конфигурациях.

Будем писать

(q, \; qw, \; Zu) \vdash (p, \; w, \; vu)

если множество D(q, a, Z) содержит (p, v), где

q, \; p \in Q, \; a \in T \cup \{e\}, \; w \in T^*, \; Z \in \Gamma^*
и
u, \; v \in \Gamma^*
(верхушка магазина слева).

Начальной конфигурацией МП-автомата M называется конфигурация вида (q0, w, Z0), где

w\in T^*
, то есть управляющее устройство находится в начальном состоянии, входная лента содержит цепочку, которую нужно проанализировать, а в магазине имеется только начальный символ Z0.

>Заключительной конфигурацией называется конфигурация вида (q, e, u), где

q \in F, u \in \Gamma^*
, то есть управляющее устройство находится в одном из заключительных состояний, а входная цепочка целиком прочитана.

Введем транзитивное и рефлексивно-транзитивное замыкание отношения

\vdash
, а также его степень k > 0 (обозначаемые
\vdash^+
,
\vdash^*
и
\vdash^k
соответственно).

Говорят, что цепочка w допускается МП-автоматом M, если

(q_0, w, Z_0) \vdash^* (q, e, u)
для некоторых
q \in F
и
u \in \Gamm^*
.

Множество всех цепочек, допускаемых автоматом M называется языком, допускаемым (распознаваемым, определяемым) автоматом M (обозначается L(M)).

Пример 4.1. Рассмотрим МП-автомат

M = ({q0, q1, q2}, {a, b}, {Z, a, b}, D, q0, Z, {q2}),




Содержание  Назад  Вперед