ВУЗ:
Составители:
3) ),(),,(
11
аqаqa → ; 8) ),(),,(
21
еqвqс → ;
4)
),(),,(
11
аqвqа → ; 9) ),(),,(
22
Вqаqa → ;
5)
),(),,(
11
вqаqв → ; 10) ),(),,(
22
Вqвqв → ;
11)
),(),,(
02
ВqqВ →
σ
.
Пример 3.5. Пусть приведенному МПА предъявляется цепочка
авсва=
α
. Последовательность вычислений МПА приведена на рис. 3.4.
Рис. 3.4.
Поскольку автомат перешел в заключительную ситуацию
),,(
0
BqB , то
m
L
∈
α
.
Заметим, что если автомату предъявить цепочку
авсвв
=
β
, то в четвертом
шаге он будет находиться в ситуации
),,(
2
аqв
, которой нет среди множества
команд. Поэтому МПА остановится, а на рабочей ленте останется запись
а
σ
.
Таким образом,
m
L∉
β
. Нетрудно видеть, что описанный МПА является
детерминированным.
Говорят, что входная цепочка
∗
∈
T
V
α
порождается автоматом, если
вычисление, начинающееся с ситуации
),,(
0
σ
qB , приводит к записи
α
на
входной ленте. Поскольку входная лента N в начальный момент всегда
пустая, то начальная ситуация фактически определяется парой (q
0
,
σ
). И
1
в в а с в а
в
в
q
0
5
в в а с в а
в
q
1
в
в
σ
σ
а
в
8
в в а с в а
в
q
1
σ
а
в
В
10
в в а с в а
в
q
2
σ
а
В
в
9
в в а с в а
в
q
2
9
в в а с в а
в
q
0
8
σ
в
а
11
в в а с в а
в
q
0
σ
в в
Страницы
- « первая
- ‹ предыдущая
- …
- 57
- 58
- 59
- 60
- 61
- …
- следующая ›
- последняя »
