Курсовая работа5 / Раздел 4
.docКурсовая работа. Раздел 4.
Вариант 19
4.1.2. Построить детерминированный магазинный автомат, распознающий цепочки из множества {anbmcmdn, где n>0, m>=0}.
Автомат с магазинной памятью G=<Q, Σ, Γ, δ, q0, Z0, F>
Q={q0, q1, q2, q3, q4}.
{a,b,c,d}
Г={a}
-
<q0, a, Z> = (q1, a)
-
<q1, a, a> = (q1, aa);
-
<q1, b, a> = (q2, ba);
-
<q1, d, a> = (q4, );
-
<q2, b, b> = (q2, bb);
-
<q2, c, b>= (q3, a);
-
<q3, c, b>= (q3, a);
-
<q3, d, a>= (q4, );
-
<q4, d, a>= (q4, );
-
<q4, , Z>= (q0, );
Рассмотрим работу этого автомата на цепочке
aaabbccddd
(q0, aaabbccddd, Z) ˫
(q1, aabbccddd,a) ˫
(q1, abbccddd,aa) ˫
(q1, bbccddd,aaa) ˫
(q2, bccddd,baaa) ˫
(q2, ccddd,bbaaa) ˫
(q3, cddd,baaa) ˫
(q3, ddd,aaa) ˫
(q4, dd,aa) ˫*
(q4, d,a) ˫*
(q4, , Z) ˫
(q0, ε, ε)
4.2.2. Построить детерминированный преобразователь с магазинной памятью, осуществляющий перевод цепочек из множества { anbmcn, где n>0, m>=0} в множество {1n+m}.
P = <Q, , Г, , , q0, Z0, F>
Q = {q0, q1, q2 q3}.
{a,b,c}
Г = {a}
= {1}
<q0, a, Z>= (q1, a, 1);
<q1, a, a>= (q1, aa, 1);
<q1, b, a>= (q2, a, 1);
<q1, c, a>= (q2, , );
<q2, b, a>= (q2, a, 1);
<q2, c, a>= (q3, , );
<q3, c, a>= (q1, , );
<q3, , Z>= (q0, , );
Рассмотрим работу этого автомата на цепочке
aabcc
(q0, aabcc, Z, ) ˫
(q1, abcc, a, 1) ˫
(q1, bcc, aa, 11) ˫
(q2, cc, aa, 111) ˫
(q3, c, a, 111) ˫
(q3, , Z, 111) ˫
(q0, ε, ε, 111)