Автоматы с магазинной памятью — страница 2

  • Просмотров 3963
  • Скачиваний 397
  • Размер файла 10
    Кб

отличаются от автоматов с магазинной памятью нали­чием выходной ленты. Далее будем рассматривать только недетерминированные магазин­ные автоматы. Рассмотрим интерпретацию функции δ для такого автомата. Эту функцию можно представить совокупностью команд вида (q, a, z)→(q1, γ1),…,(qm, γm), где q, q1,…qm Є Q, a Є V, z Є VM, γ1,…,γm Є V*m При этом считается, что если на входе читающей головки авто­ мата находится символ а, автомат

находится в состоянии q, а верхний символ рабочей ленты z, то автомат может перейти к состоянию qi, записав при этом на рабочую ленту цепочку γi(1 ≤ i ≤ m) вместо символа z, передвинуть входную головку на один символ вправо так, как это показано на рис. 1, и перейти в состояние qi. Крайний левый символ γi должен при этом оказаться в верхней ячейке магазина. Команда (q, e, z)→(q1, γ1),…, (qm, γm) означает, что независимо от входного

символа и, не передвигая входной го- + ловки, автомат перейдет в состояние qi, заменив символ z магазина на цепочку γi(1 ≤ i ≤ m). • Ситуацией магазинного автомата называется пара (q, γ), где q Є Q, γ Є V*m. Между ситуациями магазинного автомата (q, γ) и (q’, γ’), устанавливается отношение, обозначаемое символом ├, если среди команд найдется такая, что (q, a, z)→(q1, γ1),…,(qm, γm), причем γ = zβ, γ’ = γiβ q' = qi для

некоторого 1 ≤ i ≤ m (z Є Vm, β Є V*m ). Говорят, что магазинный автомат переходит из состояния (q, γ) в состояние (q’, γ’) и обозначают это следующим образом: a: (q, γ)├ (q’, γ’). Вводится и такое обозначение: a1...an: (q, γ)├ * (q’, γ’), если справедливо, что ai: (qi, γi)├ (qi+1, γi+1), 1 ≤ i ≤ m где ai Є V, γ1 = γ, γ2,…, γn+1 = γ’ Є V*m q1 = q, q2,…, qn+1 = q’ Є Q Существует два способа определения языка, допускаемого ма­газинным

автоматом. Согласно первому способу считается, что входная цепочка α Є V* принадлежит языку L1 (M) тогда, когда после просмотра последнего символа, входящего в эту цепочку, в магазине автомата М будет находиться пустая цепочка ε. Другими словами, L1 (M) = { α | α: (q0, z0) ├ * (q, ε)} где q Є Q. Согласно второму способу считается, что входная цепочка при­надлежит языку L2 (M) тогда, когда после просмотра последнего символа, входящего в

эту цепочку, автомат М окажется в одном из своих заключительных состояний qf Є F. Другими словами, L2 (M) = { α | α: (q0, z0) ├ * (qf, γ)} где γ Є V*m, qf Є F Доказано, что множество языков, допускаемых произвольными магазинными автоматами согласно первому способу, совпадает с множеством языков, допускаемых согласно второму способу. Доказано также, что если L (G2) — бесконтекстный язык, по­рождаемый Грамматикой G2 = (Vx, VT, Р, S), являющейся