ПРЕОБРАЗОВАНИЕ РАСПОЗНАВАТЕЛЯ С МАГАЗИННОЙ ПАМЯТЬЮ И КОНЕЧНЫМ МНОЖЕСТВОМ СОСТОЯНИЙ В РАСПОЗНАВАТЕЛЬ С ОДНИМ СОСТОЯНИЕМ
Аннотация и ключевые слова
Аннотация (русский):
В статье рассматривается задача распознавания контекстно-свободных языков. Для ее решения используются распознаватели с магазинной памятью, которые могут иметь конечное множество состояний. В работе определяется класс распознавателей с магазинной памятью и конечным множеством состояний, которые могут быть преобразованы в эквивалентные распознаватели с магазинной памятью и одним состоянием без увеличения мощности множества магазинных символов. Приводятся их формальные описания и на их основе – правила выполнения преобразования. Представлен пример преобразования распознавателя с конечным числом состояний в распознаватель с одним состоянием. Приводятся протоколы работы распознавателей при обработке входной цепочки, подтверждающие правильность выполненных преобразований. Распознаватель с одним состоянием в процессе распознавания анализирует только входную цепочку и содержимое магазина. Это позволяет сократить количество параметров, определяющих поведение распознавателя с магазинной памятью. Распознаватель с одним состоянием имеет более компактное представление, чем распознаватель с конечным множеством состояний.

Ключевые слова:
контекстно-свободный язык, распознаватель с магазинной памятью, состояние, эквивалентные преобразования
Текст
Текст произведения (PDF): Читать Скачать

Одной из важных задач обработки формальных языков является задача распознавания, которая заключается в определении принадлежности заданной цепочки заданному языку. Для решения задачи распознавания контекстно-свободных языков используются распознаватели с магазинной памятью (МП–распознаватели)
[1–7]. МП-распознаватель можно представить устройством, изображенным на рис. 1.

 

МП-распознаватель.tif

Рис. 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 (ax) = отвергнуть.

Рассмотрим конфигурацию (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.


Войти или Создать
* Забыли пароль?