Одной из важных задач обработки формальных языков является задача распознавания, которая заключается в определении принадлежности заданной цепочки заданному языку. Для решения задачи распознавания контекстно-свободных языков используются распознаватели с магазинной памятью (МП–распознаватели)[1–7]. МП-распознаватель можно представить устройством, изображенным на рис. 1.  Рис. 1. МП-распознаватель  В работе [8] представлен алгоритм синтеза МП–распознавателей с конечным числом состояний, которые формально можно представить следующим образом:МПn = (Qn, Sn, Гn, In, Sn, Pn, En, δn, λn, q0n, qn, γ0n),где Qn – конечное множество состояний, Qn = {q0n, q1n,…, qmn}; Sn – конечное множество входных символов, включающее концевой маркер  ˧, которым заканчивается входная цепочка; Гn = Qn È {Ñ} – конечное множество магазинных символов (равно множеству состояний, дополненному маркером дна магазина Ñ); In – конечное множество операций над головкой, In = (сдвиг, держать). Операция сдвиг перемещает головку на одну позицию вправо, а держать – не изменяет положения головки; Sn – конечное множество операций над состоянием, Sn = {сост(q0n), сост(q1n),…, сост(qmn)}. Операция сост(qin) обозначает переход в состояние qin; Pn – множество операций над магазином, Pn = {зам(γ1), зам(γ2), …   зам(γi), …}. Операция зам(γi) заключается в выталкивании верхнего символа из магазина и последовательном вталкивании символов цепочки γi; En – конечное множество значений выхода, En = {допустить, отвергнуть}; q0n – начальное состояние; qn – допускающее состояние; γ0n – начальное содержимое магазина, γ0n = Ñ (магазин пуст);δn : Qn ´ Sn ´ Гn ® In ´ Sn ´ Pn  – частичная функция переходов, которая состоянию, символу входной цепочки (находящемуся под головкой) и верхнему символу магазина ставит в соответствие операцию над головкой, состоянием и магазином, причем множество видов значений на тройке (q, a, x) равно {(сдвиг, сост(p), зам(x)), (держать, сост(p), зам(xr)), (держать, сост(x), зам(ε))}, где  ε – пустая цепочка. Заметим, что на тройке (q, a, x) операция зам(x) не изменяет содержимого магазина, зам(xr) – добавляет один символ в магазин, а зам(ε) – выталкивает верхний символ из магазина.λn : Qn ´ Sn ´ Гn ® En  – частичная функция выходов, которая состоянию, символу входной цепочки (находящемуся под головкой) и верхнему символу магазина ставит в соответствие значение выхода – допустить или отвергнуть. Значение функции на тройке (q, ˧, Ñ) равно допустить, а на всех остальных, на которых функция определена — отвергнуть.Области определения функций  δn  и  λn  не пересекаются, а их объединение равно области отправления.Тройка (q, α, γ), где q – состояние, α – часть входной цепочки, начиная с символа под головкой и заканчивая концевым маркером, γ – содержимое магазина, называется конфигурацией распознавателя МПn. Исходной конфигурацией является (q0n, α0, Ñ), где α0 – вся входная цепочка (головка находится над первым символом).Пусть конфигурацией МПn является тройка (q, aα, xγ), где a – символ под головкой, x – верхний символ магазина. Если на тройке (q, a, x) определена функция переходов δn, то ее значение определяет операции над головкой, состоянием и магазином. При выполнении этих операций конфигурация изменяется. Если на тройке (q, a, x) определена функция выходов λn, то процесс распознавания заканчивается с результатом, равным значению функции λn. Такую конфигурацию назовем заключительной. Итак, работа МПn заключается в изменении конфигураций. Последней является заключительная конфигурация, в которой определяется результат распознавания.Покажем, что распознаватель МПn можно преобразовать в распознаватель МП1 с одним состоянием, который распознает тот же язык, что и МПn. Формально МП1 определим следующим образом:МП1 = (S1, Г1, I1, P1, E1, δ1, λ1, γ01),где S1 = Sn, Г1 = Гn, I1 = In, P1 = Pn, E1 = En. В МП1 только одно состояние, поэтому операция над состоянием не имеет смысла, функции переходов δ1 и выходов λ1 определяются как δ1 : S1 ´ Г1 ® I1 ´ P1  и  λ1 : S1 ´ Г1 ® E1 , а конфигурацией является двойка (α, γ).Роль состояния в МП1 будет играть верхний символ магазина, поэтому конфигурации (q, α, xγ) в МПn будет соответствовать конфигурация (α, qxγ) в МП1. Исходной конфигурации (q0n, α0, Ñ) распознавателя МПn соответствует конфигурация (α0, q0nÑ) в МП1, поэтому начальным содержимым магазина в МП1 будет q0nÑ. Определим функцию переходов δ1 так, что если на i-ом шаге обработки входной цепочки МПn находится в конфигурации (q, aα, xγ), то МП1 на этом же шаге находится в конфигурации (aα, qxγ).Пусть в конфигурации (q, aα, xγ) определена функция переходов δn, тогда в конфигурации (aα, qxγ) должна быть определена функция переходов δ1.Если δn (q, a, x) = (сдвиг, сост(p), зам(x)), то на i+1-ом шаге конфигурацией МПn будет (p, α, xγ), а ей в МП1 соответствует конфигурация (α, pxγ). Распознаватель МП1 сменит конфигурацию (aα, qxγ) на (α, pxγ), если δ1 (a, q) = (сдвиг, зам(p)).Если δn (q, a, x) = (держать, сост(p), зам(xr)), то на i+1-ом шаге конфигурацией МПn будет (p, aα, rxγ), а ей в МП1 соответствует конфигурация (aα, prxγ). Распознаватель МП1 сменит конфигурацию (aα, qxγ) на (aα, pxγ), если δ1 (a, q) = (держать, зам(rp)).Если δn (q, a, x) = (держать, сост(x), зам(ε)), то на i+1-ом шаге конфигурацией МПn будет (x, aα, γ), а ей в МП1 соответствует конфигурация (aα, xγ). Распознаватель МП1 сменит конфигурацию (aα, qxγ) на (aα, xγ), если δ1 (a, q) = (держать, зам(ε)).Если в конфигурации (q, aα, xγ) распознавателя МПn определена функция выходов λn и λn (q, a, x) = отвергнуть, тогда в конфигурации (aα, qxγ) распознавателя МП1 должна быть определена функция выходов λ1 и λ1 (a,  x) = отвергнуть.Рассмотрим конфигурацию (q, ˧, Ñ) распознавателя МПn, на которой определена функция выходов λn и λn (q, a, x) = допустить. Этой конфигурации в МП1 соответствует конфигурация (˧, qÑ) в МП1, т. е. входная цепочка закончилась и в магазине только допускающее состояние. Для того, чтобы убедиться в том, что в магазине действительно только допускающее состояние, вытолкнем его из магазина (δ1 ((˧, q) = (держать, зам(ε))) и получим конфигурацию (˧, Ñ), в которой функция выходов λ1 равна допустить (λ1 (˧, Ñ) = допустить).Таким образом, описаны правила преобразования МП-распознавателя с конечным множеством состояний в эквивалентный ему МП-распознаватель с одним состоянием.Рассмотрим пример выполнения преобразования. МП-распознаватель с конечным множеством состояний можно задать таблицей (табл. 1), состоящей из четырех столбцов. В первом столбце указывается состояние, во втором – множество входных символов, в третьем – магазинный символ или пусто. Если МП-распознаватель находится в конфигурации (q, aα, xγ) и в таблице есть строка, в которой в первом элементе (столбце) записано состояние q, во втором – множество, содержащее символ a, в третьем – символ x или пусто, то в четвертом столбце записаны действия, которые должен выполнить распознаватель. Для сокращения таблицы в четвертом столбце не указывается операция над головкой держать, которая не изменяет положения головки, не указывается операция зам(x), которая не изменяет содержимого магазина, операция зам(ε) записывается как вытолкнуть, а операция зам(xr) – как втолкнуть(r). Если же МП-распознаватель находится в конфигурации (q, aα, xγ) и в таблице нет строки, в которой в первом элементе (столбце) записано состояние q, во втором – множество, содержащее символ a, в третьем – символ x или пусто, то цепочка отвергается.В МП-распознавателе, представленном в табл. 1, состояние 1 – начальное, состояние 4 – допускающее, начальное содержимое магазина – магазин пуст.В табл. 2 представлен протокол работы МП-распознавателя (табл. 1) при обработке цепочки adedc┤.  Таблица 1МП-распознаватель с конечным множеством состоянийТекущее состояниеВходные символыВерх магазинаДействия1a сдвиг, сост(3)1b, c, d, e сост(5), втолкнуть(2)2c сдвиг, сост(4)3d, e сост(9), втолкнуть(4)4d, e сост(9), втолкнуть(2)4┤Ñдопустить5b сдвиг, сост(6)5c2сост(2), вытолкнуть5d, e сост(9), втолкнуть(7)6d, e сост(9), втолкнуть(8)7d сдвиг, сост(8)8с2сост(2), вытолкнуть8a сдвиг, сост(5)9e сдвиг, сост(10)9d сдвиг, сост(11)10d, e сост(9), втолкнуть(11)11a, c, d, e, ┤2сост(2), вытолкнуть11a, c, d, e, ┤4сост(4), вытолкнуть11a, c, d, e, ┤7сост(7), вытолкнуть11a, c, d, e, ┤8сост(8), вытолкнуть11a, c, d, e, ┤11сост(11), вытолкнуть Таблица 2Протокол работы МП-распознавателяШагСостояниеСимволМагазинДействие11aÑсдвиг, сост(3)23dÑсост(9), втолкнуть(4)39d4 Ñсдвиг, сост(11)411e4 Ñсост(4), вытолкнуть54eÑсост(9), втолкнуть(2)69e2 Ñсдвиг, сост(10)710d2 Ñсост(9), втолкнуть(11)89d11 2Ñсдвиг, сост(11)911c11 2 Ñсост(11), вытолкнуть1011c2 Ñсост(2), вытолкнуть112cÑсдвиг, сост(4)124┤Ñдопустить В результате выполнения преобразования получим МП-распознаватель с одним состоянием, который можно задать таблицей (табл. 3), строки которой соответствуют магазинным символам и маркеру дна, а столбцы – входным символам и концевому маркеру. В клетке таблицы, находящейся в строке x и столбце a, записывается значение функции перехода или выхода на паре (a, x). Для того, чтобы не загромождать таблицу, операции держать и отвергнуть записывать не будем, а операцию зам(ε) будем записывать как вытолкнуть. Начальным содержимым магазина МП-распознавателя (табл. 3) будет 1 Ñ. Таблица 3МП-распознаватель с одним состоянием abcde┤1зам (3) сдвигзам (2 5)зам (2 5)зам (2 5)зам (2 5) 2  зам (4) сдвиг   3   зам (4 9)зам (4 9) 4   зам (2 9)зам (2 9)вытолкнуть5 зам (6) сдвигвытолкнутьзам (7 9)зам (7 9) 6   зам (8 9зам (8 9) 7   зам (8)сдвиг  8зам (5)сдвиг вытолкнуть   9   зам (11)сдвигзам (10)сдвиг 10   зам (11 9)зам (11 9) 11вытолкнуть вытолкнутьвытолкнутьвытолкнутьвытолкнутьÑ     допустить  В табл. 4 представлен протокол работы МП-распознавателя (табл. 3) при обработке цепочки adedc┤. Сравнивая протоколы работы распознавателей можно сделать вывод о том, что на каждом шаге работы содержимое магазина МП-распознавателя с одним состоянием отличается от содержимого магазина МП-распознавателя с множеством состояний на соответствующем шаге только наличием в вершине магазина текущего состояния МП-распознавателя с множеством состояний.Таким образом, в статье описаны правила преобразования МП-распознавателя с конечным множеством состояний в эквивалентный ему МП-распознаватель с одним состоянием, который в процессе распознавания анализирует только входную цепочку и содержимое магазина. Это позволяет сократить количество параметров, определяющих поведение распознавателя с магазинной памятью. Распознаватель с одним состоянием имеет более компактное представление, чем распознаватель с конечным множеством состояний. При этом, следует отметить, устранение множества состояний не приводит к расширению множества магазинных символов. Таблица 4Протокол работы МП-распознавателя с одним состояниемШагСимволМагазинДействие1a1 ÑЗАМ(3) СДВИГ2d3 ÑЗАМ(4 9) ДЕРЖАТЬ3d9 4 ÑЗАМ(11) СДВИГ4e11 4 ÑВЫТОЛК ДЕРЖАТЬ5e4 ÑЗАМ(2 9) ДЕРЖАТЬ6e9 2 ÑЗАМ(10) СДВИГ7d10 2 ÑЗАМ(11 9) ДЕРЖАТЬ8d9 11 2 ÑЗАМ(11) СДВИГ9c11 11 2ÑВЫТОЛК ДЕРЖАТЬ10c11 2 ÑВЫТОЛК ДЕРЖАТЬ11c2 ÑЗАМ(4) СДВИГ12┤4 ÑВЫТОЛК ДЕРЖАТЬ13┤ÑДОПУСТИТЬ