![]()
|
|||
Пример 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 }.
Начальная конфигурация есть (q0, x, Z0, 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)
Пример 1.4. Пусть sdts T = ({E}, {a, +, *}, {a, +, *}, R, E), где По лемме 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, *). Проверить!
|
|||
|