Белгород, Белгородская область, Россия
В статье рассматривается задача распознавания контекстно-свободных языков. Для ее решения используются распознаватели с магазинной памятью, которые могут иметь конечное множество состояний. В работе определяется класс распознавателей с магазинной памятью и конечным множеством состояний, которые могут быть преобразованы в эквивалентные распознаватели с магазинной памятью и одним состоянием без увеличения мощности множества магазинных символов. Приводятся их формальные описания и на их основе – правила выполнения преобразования. Представлен пример преобразования распознавателя с конечным числом состояний в распознаватель с одним состоянием. Приводятся протоколы работы распознавателей при обработке входной цепочки, подтверждающие правильность выполненных преобразований. Распознаватель с одним состоянием в процессе распознавания анализирует только входную цепочку и содержимое магазина. Это позволяет сократить количество параметров, определяющих поведение распознавателя с магазинной памятью. Распознаватель с одним состоянием имеет более компактное представление, чем распознаватель с конечным множеством состояний.
контекстно-свободный язык, распознаватель с магазинной памятью, состояние, эквивалентные преобразования
Одной из важных задач обработки формальных языков является задача распознавания, которая заключается в определении принадлежности заданной цепочки заданному языку. Для решения задачи распознавания контекстно-свободных языков используются распознаватели с магазинной памятью (МП–распознаватели)
[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. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. М.: Мир. 1978. Т. 1. 612 с.
3. Льюис Ф., Розенкранц Д., Стирнз Р. Теоретические основы проектирования компиляторов. М. : Мир, 1979. 656 с.
4. Опалева Э.А., Самойленко В.П. Языки программирования и методы трансляции. СПб.: «БХВ-Петербург», 2005. 471 с.
5. Ахо А., Лам М., Сети Р., Ульман Дж. Компиляторы. Принципы, технологии и инструментарий. М: Издательский дом «Вильямс», 2008. 1185 с.
6. Серебряков, В.А. Теория и реализация языков программирования. М.: Физматлит, 2012. 233 с.
7. Поляков В.М., Рязанов Ю. Д. Алгоритм построения нерекурсивных программ-распознавателей линейной сложности по детерминированным синтаксическим диаграммам // Вестник БГТУ им. В.Г. Шухова. № 6. 2013. С. 194-199.
8. Рязанов Ю. Д. Синтез распознавателей с магазинной памятью по детерминированным синтаксическим диаграммам // Вестник ВГУ. Системный анализ и информационные технологии. 2014. №1. С. 138-145.
