ВУЗ:
Составители:
в состояние q
m
. Если просматриваемый символ входной цепочки - е, то
головка не передвигает ленту N. Если же это символ a
i
, то лента
передвигается влево таким образом, чтобы головка просматривала
следующий за ним символ. В зависимости от того, какое значение принимает
х, рабочая головка оперирует с рабочей лентой следующим образом:
а) если
σ
=
x
, то лента М передвигается на одну ячейку вправо, предыдущий
символ стирается;
б) если
e
x
= , то лента М не передвигается, символ не меняется;
в) если
y
x
= , где y - последовательность символов длиной m, то y заносится
на М, лента сдвигается на m ячеек влево и рабочая головка читает последний
символ y.
Различают два типа МПА: допускающие и порождающие языки.
Говорят, что входная цепочка
∗
∈
T
V
α
является допустимой или
представимой в МПА, если вычисление, начинающееся с этой цепочки,
заканчивается ситуацией
),,(
0
BqB . В противном случае входная цепочка не
допустима или не представима в МПА. Множество цепочек, представимых в
автомате, образуют язык, допускаемый автоматом.
Рассмотрим работу автомата, допускающего язык
}*},{/{
1
вaxxcxL
m
∈=
−
.
Любая цепочка языка L
m
, допуская вольность речи, симметрична
относительно маркера с. Поэтому работу автомата можно организовать
следующим образом. Вначале скопировать на рабочую ленту подцепочку х, а
затем сравнять содержимое рабочей ленты с подцепочкой х
-1
. Если они
совпадают, то содержимое рабочей ленты стирается, автомат переходит в
ситуацию
),,(
0
BqB . В том случае, если цепочка не принадлежит языку L
m
, на
рабочей ленте после остановки автомата остаются некоторые символы,
отличные от В. Описанную процедуру задает следующее множество команд,
однозначно определяющее МПА.
1)
),(),,(
10
σ
σ
qqa → ; 6) ),(),,(
11
вqвqв → ;
2)
),(),,(
10
вqqв →
σ
; 7) ),(),,(
21
еqаqс → ;
Страницы
- « первая
- ‹ предыдущая
- …
- 56
- 57
- 58
- 59
- 60
- …
- следующая ›
- последняя »
