Пример 2 Дано: G({+, (, ), a}, {S, A}, Р, {S}); Р: {S S+A | A, A (S) | a} Построение расширенного МП-автомата: 1) Q = {q, r}, q 0 = q, T = {+, (, ), a}, N = {+, (, ), a, S, A, #}, N 0 = #, Z = r. 2) F(q,, S+A) = (q, S), F(q,, A) = (q, S), F(q,, (S)) = (q, A), F(q,, a) = (q, A). 3) F(q, t, ) = (q, t) для t {+, (, ), a}. 4) F(q,, #S) = (r, ).
Распознавание МП-автоматом строки (а) Номер Текущее Входная Содержимое конф. состояние строка магазина 1q (a)(a)# 3 qa)a) #( q 2 )#(a 4 q )#(A q )#(S5 8 q #S#S 9 r 6q#(S) 7 q #A#A