Пример 1.4.

Вспомогательный материал к лекции №10(08 ноября 2017)

Пример 1.2. Пусть sdts

T = ({E, T, F}, {a, +, *, (, )}, {a, +, *}, R, E), где

R = {(1) E ® E + T, E T +;

(2) E ® T, T;

(3) T ® T * F, T F *;

(4) T ® F, F;

(5) F ® (E), E;

(6) F ® a, a }.

Начальная конфигурация есть (q₀, x, Z₀, e), где x обозначает всю входную цепочку.

Пример 1.3.Пустьpdt P = ({q}, {a, +, *}, {E, +, *}, {a, +, *}, d, q, E,{q}), где

1) d(q, a, E) = {( q, e, a)},

2) d(q, +, E) = {( q, EE+, e)},

3) d(q, *, E) = {( q, EE*, e)},

4) d(q, e, +) = {( q, e, +)},

5) d(q, e, *) = {( q, e, *)}.

Рассмотрим действия pdt P на входе +*aaa:

(q, +*aaa, E, e) (q, *aaa, EE+, e) (q, aaa, EE*E+, e) (q, aa, E*E+, a)

(q, a, *E+, aa) (q, a, E+, aa*) (q, e, +, aa*a) (q, e, e, aa*a+).

Пример 1.4.

Пусть sdts T = ({E}, {a, +, *}, {a, +, *}, R, E), где
R = {(1) E ® +EE, EE+ ; (2) E ® *EE, EE* ; (3) E ® a, a}.

По лемме 1.1 эквивалентный npdt есть

P = ({q}, {a, +, *}, {E, a, +, *, a’, +’, *’}, {a, +, *}, d, q, E,Æ),
где

1) d(q, e, E) = { (q, +EE+’, e), (q, *EE*’, e), (q, aa’, e)},

2) d(q, b, b) = {( q, e, e)} для всех bÎ{a, +, *},

3) d(q, e, с’) = {( q, e, с)} для всех сÎ{a, +, *}.

Пример 1.6. Пусть

T = ({E, T, F}, {a, +, *, (, )}, {a, +, *}, R, E), где R = {(1) E ® E + T,+ET; (2) E ® T, T; (3) T ® T * F,*TF; (4) T ® F, F; (5) F ® (E), E; (6) F ® a, a }.

В соответствии с описанием построений в теореме 1.3 определим детерминированный магазинный преобразователь, восстанавливающий выход трансляции по левостороннему анализу входной цепочки:

P = ({q}, {1, 2, 3, 4, 5, 6}, {E, T, F, a, +, *}, {a, +, *}, d, q, E, Æ),где

1) d(q, 1, E) = (q, +ET, e); 2) d(q, 2, E) = (q, T, e);

3) d(q, 3, T) = (q, *TF, e); 4) d(q, 4, T) = (q, F, e);

5) d(q, 5, F) = (q, E, e); 6) d(q, 6, F) = (q, a, e);

7) d(q, e, a) = (q, e, a); 8) d(q, e, +) = (q, e, +);

9) d(q, e, *) = (q, e, *).

Проверить!