Belgorod, Belgorod, Russian Federation
In this article the recognition of the problem of context-free languages is considered. Pushdown recognizers are used for its decision, which can have a finite set of states. In this work the class of pushdown recognizers and a finite set of states which can be transformed to equivalent recognizers with pushdown memory and one state without increase in power of a set of pushdown symbols. Their formal descriptions are given and on their basis rules of performance of transformation are provided. The example of transformation of the recognizer with final number of states to the recognizer with one state is presented. The records recognizers work at processing an input string, are given validating the executed transformations. The recognizer with one state in the course of recognition analyzes only the input string and the contents of the pushdown memory. It allows to reduce the number of parameters defining behavior of the recognizer with pushdown memory. The recognizer with one state has more compact idea, than the recognizer with a final set of states.
context-free language, pushdown recognizer, state, equivalent transforming
Одной из важных задач обработки формальных языков является задача распознавания, которая заключается в определении принадлежности заданной цепочки заданному языку. Для решения задачи распознавания контекстно-свободных языков используются распознаватели с магазинной памятью (МП–распознаватели)
[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
МП-распознаватель с конечным множеством состояний
|
Текущее состояние |
Входные символы |
Верх магазина |
Действия |
|
1 |
a |
|
сдвиг, сост(3) |
|
1 |
b, c, d, e |
|
сост(5), втолкнуть(2) |
|
2 |
c |
|
сдвиг, сост(4) |
|
3 |
d, e |
|
сост(9), втолкнуть(4) |
|
4 |
d, e |
|
сост(9), втолкнуть(2) |
|
4 |
┤ |
Ñ |
допустить |
|
5 |
b |
|
сдвиг, сост(6) |
|
5 |
c |
2 |
сост(2), вытолкнуть |
|
5 |
d, e |
|
сост(9), втолкнуть(7) |
|
6 |
d, e |
|
сост(9), втолкнуть(8) |
|
7 |
d |
|
сдвиг, сост(8) |
|
8 |
с |
2 |
сост(2), вытолкнуть |
|
8 |
a |
|
сдвиг, сост(5) |
|
9 |
e |
|
сдвиг, сост(10) |
|
9 |
d |
|
сдвиг, сост(11) |
|
10 |
d, e |
|
сост(9), втолкнуть(11) |
|
11 |
a, c, d, e, ┤ |
2 |
сост(2), вытолкнуть |
|
11 |
a, c, d, e, ┤ |
4 |
сост(4), вытолкнуть |
|
11 |
a, c, d, e, ┤ |
7 |
сост(7), вытолкнуть |
|
11 |
a, c, d, e, ┤ |
8 |
сост(8), вытолкнуть |
|
11 |
a, c, d, e, ┤ |
11 |
сост(11), вытолкнуть |
Таблица 2
Протокол работы МП-распознавателя
|
Шаг |
Состояние |
Символ |
Магазин |
Действие |
|
1 |
1 |
a |
Ñ |
сдвиг, сост(3) |
|
2 |
3 |
d |
Ñ |
сост(9), втолкнуть(4) |
|
3 |
9 |
d |
4 Ñ |
сдвиг, сост(11) |
|
4 |
11 |
e |
4 Ñ |
сост(4), вытолкнуть |
|
5 |
4 |
e |
Ñ |
сост(9), втолкнуть(2) |
|
6 |
9 |
e |
2 Ñ |
сдвиг, сост(10) |
|
7 |
10 |
d |
2 Ñ |
сост(9), втолкнуть(11) |
|
8 |
9 |
d |
11 2Ñ |
сдвиг, сост(11) |
|
9 |
11 |
c |
11 2 Ñ |
сост(11), вытолкнуть |
|
10 |
11 |
c |
2 Ñ |
сост(2), вытолкнуть |
|
11 |
2 |
c |
Ñ |
сдвиг, сост(4) |
|
12 |
4 |
┤ |
Ñ |
допустить |
В результате выполнения преобразования получим МП-распознаватель с одним состоянием, который можно задать таблицей (табл. 3), строки которой соответствуют магазинным символам и маркеру дна, а столбцы – входным символам и концевому маркеру. В клетке таблицы, находящейся в строке x и столбце a, записывается значение функции перехода или выхода на паре (a, x). Для того, чтобы не загромождать таблицу, операции держать и отвергнуть записывать не будем, а операцию зам(ε) будем записывать как вытолкнуть. Начальным содержимым магазина МП-распознавателя (табл. 3) будет 1 Ñ.
Таблица 3
МП-распознаватель с одним состоянием
|
|
a |
b |
c |
d |
e |
┤ |
|
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
Протокол работы МП-распознавателя с одним состоянием
|
Шаг |
Символ |
Магазин |
Действие |
|
1 |
a |
1 Ñ |
ЗАМ(3) СДВИГ |
|
2 |
d |
3 Ñ |
ЗАМ(4 9) ДЕРЖАТЬ |
|
3 |
d |
9 4 Ñ |
ЗАМ(11) СДВИГ |
|
4 |
e |
11 4 Ñ |
ВЫТОЛК ДЕРЖАТЬ |
|
5 |
e |
4 Ñ |
ЗАМ(2 9) ДЕРЖАТЬ |
|
6 |
e |
9 2 Ñ |
ЗАМ(10) СДВИГ |
|
7 |
d |
10 2 Ñ |
ЗАМ(11 9) ДЕРЖАТЬ |
|
8 |
d |
9 11 2 Ñ |
ЗАМ(11) СДВИГ |
|
9 |
c |
11 11 2Ñ |
ВЫТОЛК ДЕРЖАТЬ |
|
10 |
c |
11 2 Ñ |
ВЫТОЛК ДЕРЖАТЬ |
|
11 |
c |
2 Ñ |
ЗАМ(4) СДВИГ |
|
12 |
┤ |
4 Ñ |
ВЫТОЛК ДЕРЖАТЬ |
|
13 |
┤ |
Ñ |
ДОПУСТИТЬ |
1. Schutzenberger M.P. «On context-free languages and pushdown automata», Information and Control 6:3 (1963). pp. 246. 264.
2. Aho A., Ul'man Dzh. Teoriya sintaksicheskogo analiza, perevoda i kompilyacii. M.: Mir. 1978. T. 1. 612 s.
3. L'yuis F., Rozenkranc D., Stirnz R. Teoreticheskie osnovy proektirovaniya kompilyatorov. M. : Mir, 1979. 656 s.
4. Opaleva E.A., Samoylenko V.P. Yazyki programmirovaniya i metody translyacii. SPb.: «BHV-Peterburg», 2005. 471 s.
5. Aho A., Lam M., Seti R., Ul'man Dzh. Kompilyatory. Principy, tehnologii i instrumentariy. M: Izdatel'skiy dom «Vil'yams», 2008. 1185 s.
6. Serebryakov, V.A. Teoriya i realizaciya yazykov programmirovaniya. M.: Fizmatlit, 2012. 233 s.
7. Polyakov V.M., Ryazanov Yu. D. Algoritm postroeniya nerekursivnyh programm-raspoznavateley lineynoy slozhnosti po determinirovannym sintaksicheskim diagrammam // Vestnik BGTU im. V.G. Shuhova. № 6. 2013. S. 194-199.
8. Ryazanov Yu. D. Sintez raspoznavateley s magazinnoy pamyat'yu po determinirovannym sintaksicheskim diagrammam // Vestnik VGU. Sistemnyy analiz i informacionnye tehnologii. 2014. №1. S. 138-145.
