ВУЗ:
Составители:
вообще, в каждом шаге работа порождающего МПА определяется частичной
ситуацией (q, A
k
). Команда порождающего МПА имеет вид ),,(),( xqaAq
miki
→ ,
где q
i
, q
m
- состояния МПА,
Ak
VA
∈
,
AT
VVx U
∈
, а буква a
i
порождается
(генерируется) на входной ленте. Порождающий МПА выдает на входную
ленту правильную цепочку всякий раз, когда, исходя из записанной выше
начальной ситуации, он возвращается в состояние q
0
, причем в этот момент
рабочая лента М оказывается пустой и МПА оказывается в заключительной
ситуации
),,(
0
BqB .
Рассмотрим работу автомата, порождающего цепочки языка L
m
.
Множество команд такого автомата имеет вид:
1)
),,(),(
10
aqaq →
σ
; 7) ),,(),(
21
eqcaq → ;
2)
),,(),(
10
вqвq →
σ
; 8)
),,(),(
21
еqсвq →
;
3)
),,(),(
11
aqaаq → ; 9) ),,(),(
22
Вqaаq → ;
4)
),,(),(
11
aqaвq → ; 10) ),,(),(
22
Вqввq → ;
5)
),,(),(
11
вqваq → ; 11) ),,(),(
02
ВqВq →
σ
.
6)
),,(),(
11
вqввq →
;
Пример 3.6. Запишем процесс порождения цепочки
авсва=
α
МПА,
имеющим описанное выше множество команд. Последовательность
вычислений МПА приведена на рис. 3.5.
Рис. 3.5.
1
В
В В В В
а
В
q
0
В
σ
5
В
В а В
q
1
В
σ
7
В
в а В В
q
1
В
в
σ
а
10
В
в а с В
q
2
В
в
σ
а
9
В
в а с в
q
2
В
а
В
В
σ
11
В
в а с в
q
2
В
σ
а
В
В
в а с в
q
0
В
В
а
Страницы
- « первая
- ‹ предыдущая
- …
- 58
- 59
- 60
- 61
- 62
- …
- следующая ›
- последняя »
