Задание

Задание

Построить детерминированный автомат с магазинной памятью P (с опустошением стека), допускающий язык L(P) = {a n b k c n | k > 0, n ≥ 0}. Построить КС-грамматику для этого же языка.

Пример решения другого варианта

Построить детерминированный автомат с магазинной памятью P (с опустошением стека), допускающий язык L(P) = {a 2k b n c n | k > 0, n > 0}. Построить КС-грамматику для этого же языка.

Для распознавания четного количества символа «a» введем переходы

δ(q0,a, Z)={(q1,Z)} , δ(q1,a, Z)={(q2,Z)}, δ(q2,a, Z)={(q1,Z)}. Если префикс  входа состоит из четного количества «a»( ненулевого), то символ «b», если он есть, автомат встретит в состоянии  q2  . Далее все символы «b» заносим в стек

δ(q2,b, Z)={(q3,bZ)}, δ(q3,b, b)={(q3,bb)}. Все последующие символы «c» используются для выталкивания из стека символов «b».

δ(q3,c, b)={(q4, λ)},δ(q4,c, b)={(q4, λ)}. Если количества «b» и «c» совпадают,

То после прочтения входной цепочки в стеке будет символ Z.

δ(q4, λ,Z)={(q5, λ)}.

Автомат P({q0,q1,q2,q3,q4,q5},{a, b,c},{Z, b},δ,q0,Z,{q5}), где δ описана выше.

Введем нетерминал A для вывода a2k, k>0: A → Aaa | aa и нетерминал B для вывода bncn, n>0: B → bBc | bc.. Грамматика

G({a, b,c},{S, A,B},P, S), где P:

S → AB

A → Aaa | aa

B → bBc | bc.