ВУЗ:
Составители:
маркер или из входного словаря V
Т
. Управляющее устройство может
принимать одно из состояний множества
},...,,{
10 n
qqqQ
=
.
Схематический МПА представлен на рис. 3.3.
Рис. 3.3.
Физической ситуацией называется тройка
),,(
kji
вqa , где Va
i
∈ ,
j
q -
состояние,
TAm
VVB U∈ . Ситуацией МПА называется либо физическая
ситуация, либо тройка, полученная из нее заменой a
i
, или в
k
, или обоих сразу
на единый символ е. Если МПА находится в ситуации
∑
= ),,(
kji
вqa ,
считается, что он находится одновременно в четырех ситуациях: 1)
),,(
kji
вqa ,
2)
),,(
kj
вqe , 3) ),,( eqa
ji
, 4) ),,( eqe
j
.
Командой МПА называется выражение типа
∑
→ ),( xq
i
, где х - либо е,
либо
σ
, либо цепочка в
TA
VV U . Для задания некоторого МПА необходимо
задать множество команд
∑
→ ),(
kii
xq . В общем случае МПА может быть как
детерминированным, так и недерминированным автоматом.
МПА работает следующим образом. Перед началом работы на ленту N
заносится анализируемая цепочка из входного алфавита. Автомат находится
в начальном состоянии q
0
. Входная головка рассматривает самый левый
символ цепочки, рабочая головка - символ
σ
, записанный в самой левой
ячейке ленты. Таким образом,
),,(
0
σ
qa
i
- начальная ситуация МПА. Пусть
автомат перешел в некоторую ситуацию ∑. Если ∑ такова, что среди команд
автомата нет команды, начинающейся с ∑, то автомат останавливается. Если
в МПА имеется несколько команд, начинающихся с ∑, то автомат выбирает
любую из них. В этом случае он работает как недерминированный автомат.
Пусть выбрана
команда
∑
→ ),( xq
m
. Тогда устройство управления переходит
q
0
, q
1
,…,q
n
N
В
a
i
a
j
a
j+1
…
…
a
е
В
σ
A
j
…
A
r
В
А
A
j+1
М
Страницы
- « первая
- ‹ предыдущая
- …
- 55
- 56
- 57
- 58
- 59
- …
- следующая ›
- последняя »
