Белгород, Белгородская область, Россия
В статье рассматривается задача эквивалентного преобразования распознавателя с магазинной памятью и одним состоянием в более компактный распознаватель. Уменьшение размера распознавателя достигается за счет сокращения количества магазинных символов. Для сокращения количества магазинных символов вводится отношение на множестве этих символов, обладающее свойством эквивалентности, такое, что “стягивание” класса эквивалентности в один символ дает распознаватель, эквивалентный исходному. Предложен алгоритм разбиения множества магазинных символов на классы эквивалентности и алгоритм построения распознавателя, эквивалентного исходному, но с меньшим (не большим) количеством магазинных символов. Предложенный алгоритм может быть использован при разработке программ обработки формальных языков.
контекстно-свободный язык, распознаватель с магазинной памятью, магазинный символ, переход, эквивалентные преобразования.
Введение. В теории формальных языков важное место занимают контекстно-свободные языки, проблема распознавания для которых решается с помощью распознавателей с магазинной памятью (МП-распознаватели) [1–6]. В работе рассматривается один из классов МП-распознавателей с одним состоянием. Два различных МП-распознавателя называются эквивалентными, если равны распознаваемые ими языки. Эквивалентные МП-распознаватели могут иметь разный размер. На практике предпочтение отдается распознавателям меньшего размера. Уменьшить размер МП-распознавателя с одним состоянием можно за счет сокращения магазинных символов. В работе решается задача преобразования заданного МП-распознавателя с одним состоянием в эквивалентный ему распознаватель с меньшим (не большим) количеством магазинных символов. Для решения этой задачи вводится отношение на множестве магазинных символов МП-распознавателя, обладающее свойством эквивалентности, показывается, что преобразование МП-распознавателя, заключающееся в “стягивании” пары символов, принадлежащих введенному отношению, в один символ, не изменяет распознаваемого языка, т. е. является эквивалентным преобразованием. Отсюда следует, что “стягивание” класса эквивалентности в один символ также является эквивалентным преобразованием. Предлагается алгоритм разбиения множества магазинных символов МП-распознавателя на классы эквивалентности и алгоритм построения МП-распознавателя, эквивалентного исходному, с не большим количеством магазинных символов, чем исходный МП-распознаватель.
Определение распознавателя с магазинной памятью и одним состоянием. В работе будем рассматривать класс МП-распознавателей [7 – 9], которые можно построить по диаграммам Вирта [7] или синтаксическим диаграммам с многовходовыми компонентами [10]. МП-распознаватель из этого класса формально можно представить следующим образом:
М = (X, Г, I, P, W, δ, λ, g0, γ0) ,
где X – конечное множество входных символов, включающее концевой маркер ˧, которым заканчивается входная цепочка, Х = {х1, х2,…, хn, ˧};
Г – конечное множество магазинных символов, включающее маркер дна магазина Ñ, Г = {g0, g1, g2,…, gm, Ñ}; I – конечное множество операций над головкой, I = (сдвиг, держать); P – множество операций над магазином,
P = {заменить(gi) | gi Î Г} È {заменить(gi gj) | gi Î Г и gj Î Г } È {вытолкнуть} È {не изменять}.
W – конечное множество значений выхода, W = {допустить, отвергнуть};g0 – начальный символ магазина, g0 Î Г; γ0 – начальное содержимое магазина, γ0 = Ñg0 (магазин содержит маркер дна и начальный символ магазина);
δ : X ´ Г ® P ´ I – частичная функция переходов, которая символу входной цепочки (находящемуся под головкой) и верхнему символу магазина ставит в соответствие операцию над головкой и магазином, причем множество видов значений на двойке (x, gs) равно {(заменить(gi), сдвиг), (заменить(gi gj), держать), (втолкнуть, держать)}. Если значение функции на двойке (x, gs) равно (заменить(gi), сдвиг), то такой переход будем обозначать (gs, x, (gi,®)), если значение функции на этой двойке равно (заменить(gi gj), держать), то переход обозначим (gs, x, (gi gj)), если же значение на этой двойке равно (втолкнуть, держать), то переход обозначим (gs, x, ).
λ : X ´ Г ® W – частичная функция выходов, которая символу входной цепочки (находящемуся под головкой) и верхнему символу магазина ставит в соответствие значение выхода – допустить или отвергнуть. Значение функции на двойке (˧, Ñ) равно допустить, а на всех остальных, на которых функция определена – отвергнуть.
Области определения функций δ и λ не пересекаются, а их объединение равно области отправления.
Двойка (α, Ñγ), где α – часть входной цепочки, начиная с символа под головкой и заканчивая концевым маркером, γ – содержимое магазина, называется конфигурацией МП-распознавателя. Исходной конфигурацией является (α0, Ñ g0), где α0 – вся входная цепочка (головка находится над первым символом).
Пусть конфигурацией МП-распознавателя является двойка (xα, Ñγgs), где x – символ под головкой, gs – верхний символ магазина. Если на двойке (x, gs) определена функция переходов δ, то ее значение определяет операции над головкой и магазином. При выполнении этих операций конфигурация изменяется. Если на двойке (x, qs) определена функция выходов λ, то процесс распознавания заканчивается с результатом, равным значению функции λ. Такую конфигурацию назовем заключительной. Итак, работа МП-распознавателя заключается в изменении конфигураций. Последней является заключительная конфигурация, в которой определяется результат распознавания.
МП-распознаватель с одним состоянием можно задать таблицей T, в которой строки соответствуют входным символам, а столбцы – магазинным символам. Клетку таблицы T в строке x и столбце gs будем обозначать Т[x, gs]. Клетки таблицы T заполняются по следующим правилам. Если на паре (x, gs) определен переход (gs, x, (gi,®)), то в клетку Т [x, gs] запишем (gi,®), если определен переход (gs, x, (gi gj)), то в клетку Т[x, gs] запишем (gi gj), и, если определен переход (gs, x, ), то в клетку Т[x, gs] запишем . В клетку Т [˧, Ñ] запишем «доп», она соответствует выходу допустить. Пустые клетки соответствуют выходу отвергнуть. Пример МП-распознавателя представлен в табл.1.
Таблица 1
Таблица МП-распознавателя
|
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
Ñ |
|
a |
4 ® |
6 ® |
9 ® |
10,2 |
11,3 |
12,2 |
|
13,3 |
16 ® |
14 ® |
|
15 ® |
|
|
|
|
|
|
b |
5 ® |
7 ® |
8 ® |
10,2 |
11,3 |
12,2 |
15 ® |
13,3 |
|
|
14 ® |
|
16 ® |
|
|
|
|
|
˧ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
доп |
Для обеспечения большей возможности сокращения количества магазинных символов, преобразуем МП-распознаватель следующим образом: если в какой либо клетке некоторого столбца распознавателя записан символ , то все пустые клетки этого столбца заполнить символом . Такое преобразование не изменит распознаваемого языка, оно лишь отложит обнаружение ошибки на некоторое число шагов, причем без продвижения по входной цепочке. Выполнив это преобразование для МП-распознавателя (табл. 1), получим МП-распознаватель, представленный в табл. 2.
Таблица 2
Таблица МП-распознавателя
|
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
Ñ |
|
a |
4 ® |
6 ® |
9 ® |
10,2 |
11,3 |
12,2 |
|
13,3 |
16 ® |
14 ® |
|
15 ® |
|
|
|
|
|
|
b |
5 ® |
7 ® |
8 ® |
10,2 |
11,3 |
12,2 |
15 ® |
13,3 |
|
|
14 ® |
|
16 ® |
|
|
|
|
|
˧ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
доп |
Отношение R на множестве магазинных символов, обладающее свойством эквивалентности. Пара символов gm и gm' принадлежит отношению R если:
1) переход (gm, х, (gi , ®)) существует тогда и только тогда, когда существует переход (gm', х, (gi', ®)) и (gi, gi') Î R;
2) переход (gm, х, (gi , gj)) существует тогда и только тогда, когда существует переход (gm', х, (gi', gj')) и (gi, gi') Î R и (gj, gj') Î R;
3) переход (gm, х, ) существует тогда и только тогда, когда существует переход (gm', х, ).
Это отношение рефлексивно, симметрично и транзитивно.
Пару (gm, gm') Î R будем называть парой эквивалентных символов или говорить, что символы gm и gm' эквивалентны.
Из третьего условия эквивалентности состояний следует, что если для символов gm и gm' существуют только переходы с выполнением операции вытолкнуть, то символы gm и gm' эквивалентны. В остальных же случаях для эквивалентности символов gm и gm' необходима эквивалентность других пар символов.
Эквивалентное преобразование распознавателя с магазинной памятью, сокращающее количество магазинных символов. Рассмотрим МП-распознаватель М1, в котором есть пара эквивалентных магазинных символов (gm, gm'), представленный в виде таблицы.
Построим таблицу МП-распознавателя М2 следующим образом:
1) возьмем таблицу МП-распознавателя М1 и удалим в ней столбец, соответствующий магазинному символу gm;
2) все вхождения символа gm в таблице распознавателя заменим на gm'.
Такое преобразование МП-распознавателя М1 условно можно назвать “стягиванием” символов gm и gm' в один символ gm'.
Пусть МП-распознаватели М1 и М2 обрабатывают цепочку α и на некотором шаге вверху магазина распознавателя М1 оказался символ gm, а вверху магазина распознавателя М2 — символ gm'. К этому моменту МП-распознаватели М1 и М2 обработали одинаковое количество символов цепочки α и содержимое магазинов этих распознавателей одинаковое. Из определения эквивалентности символов gm и gm' следует:
1) если М1 выполнит переход (gm, х, (gi , ®)), то М2 выполнит переход (qm', х, (gi', ®)), после чего верхние символы в магазинах распознавателей М1 и М2 будут эквивалентными и распознаватели будут обрабатывать символ входной цепочки, следующий за символом х;
2) если М1 выполнит переход (gm, х, (gi , gj)), то М2 выполнит переход (gm', х, (gi', gj')), после чего в магазинах эквивалентными будут верхние символы, и символы, находящиеся непосредственно под верхними символами и распознаватели будут обрабатывать тот же символ х входной цепочки;
3) если М1 выполнит переход (gm, х, ), то М2 выполнит переход (gm', х, ), после чего вверху магазинов будут эквивалентные (или одинаковые) символы и распознаватели будут обрабатывать тот же символ х входной цепочки;
4) если М1 отвергнет цепочку α, то М2 также отвергнет эту цепочку.
Таким образом, на каждом шаге работы МП-распознавателей М1 и М2 :
1) обработанная часть цепочки α распознавателем М1 равна обработанной части цепочки α распознавателем М2;
2) количество символов в магазине распознавателя М1 равно количеству символов в магазине распознавателя М2, причем i-й символ в магазине распознавателя М1 эквивалентен (или равен) i-му символу в магазине распознавателя М2.
Следовательно, если цепочка α допускается (отвергается) одним из распознавателем, то она допускается (отвергается) другим распознавателем, т. е. распознаватели М1 и М2 распознают один и тот же язык.
Если в МП-распознавателе существует класс эквивалентных магазинных символов, в котором количество символов больше двух, то последовательное “стягивание” пар эквивалентных символов приведет к “стягиванию” класса эквивалентных символов в один символ. “Стягивание” каждого класса эквивалентных символов в один символов позволяет сократить количество магазинных символов МП-распознавателя.
Разбиение множества магазинных символов на классы эквивалентности по отношению R. Отношение R обладает свойством эквивалентности и определяет разбиение множества магазинных символов МП-распознавателя на классы эквивалентности. Для разбиения множества магазинных символов на классы эквивалентности применим следующий метод.
С учетом условий принадлежности пары символов отношению R будем последовательно разбивать множество магазинных символов на подмножества так, чтобы неэквивалентные символы попали в различные подмножества.
Рассмотрим более детально условия принадлежности пары символов (gm, gm',) отношению R.
Первое условие.
Первое условие состоит из двух частей:
1 часть: переход (gm, х, (gi , ®)) существует тогда и только тогда, когда существует переход (gm', х, (gi', ®));
2 часть: (gi, gi') Î R.
Это условие истинно, если истинны обе части.
Второе условие.
Второе условие состоит из двух частей:
1 часть: переход (gm, х, (gi , gj)) существует тогда и только тогда, когда существует переход (gm', х, (gi', gj'));
2 часть: (gi, gi') Î R и (gj, gj') Î R.
Это условие истинно, если истинны обе части.
Третье условие.
Переход (gm, х, ) существует тогда и только тогда, когда существует переход (gm', х, ).
Сначала разобьем множество магазинных символов на подмножества так, чтобы для любых двух символов подмножества истинными были третье условие и только первые части первых двух условий. Для МП-распознавателя (см. табл. 2) это будут подмножества: G1 = {1,2,3}, G2 = {4,5,6,8}, G3 = {7,11,13}, G4 = {9,10,12}, G5 = {14,15,16}. Эти подмножества образуют разбиение Н = { G1, G2, G3, G4, G5}.
Символы, принадлежащие различным подмножествам, явно неэквивалентны, но два символа из одного подмножества могут быть неэквивалентными, так как при разбиении мы не учитывали вторые части первого и второго условия принадлежности пары символов отношению R.
Для учета вторых частей условий построим таблицу S, в которой столбцы соответствуют магазинным символам МП-распознавателя (не включая маркер дна), а строки – входным символам (включая концевой маркер).
Клетку таблицы S в строке х и столбце gm будем обозначать S[х, gm].
Переходу (gm, х, (gn , ®)) соответствует клетка S[х, gm]. Если gn Î Gi, то в клетку S[х, gm] запишем i. Если символы gm и gm' принадлежат одному подмножеству и существуют переходы (gm, х, (gn, ®)) и (gm', х, (gn', ®)) и S[х, gm] ¹ S[х, gm'], то это говорит о ложности второй части первого условия и, следовательно, (gm, gm',) Ï R и символы gm и gm' нужно включить в разные подмножества нового разбиения Н'.
Переходу (gm, х, (gs, gn)) соответствует клетка S[х, gm]. Если gs Î Gi и gn Î Gj, то в клетку S[х, gm] запишем (i, j). Если символы gm и gm' принадлежат одному подмножеству и существуют переходы (gm, х, (gs, gn)) и (gm', х, (gs', gn')) и S[х, gm] ¹ S[х, gm'], то это говорит о ложности второй части второго условия и, следовательно, (gm, gm',) Ï R и символы gm и gm' нужно включить в разные подмножества нового разбиения H'.
Анализируя таблицу S, формируем новое разбиение H'. Подмножество Gi' разбиения H' формируется из элементов некоторого подмножества Gj разбиения H. Gi' является максимальным по мощности подмножеством множества Gj, таким, что для каждой пары символов gm и gm', принадлежащих подмножеству Gi', для всех строк l таблицы S верно, что S [l, gm] = S [l, gm'].
Если H' ¹ H, то принимаем, что H = H', заново строим таблицу S по описанным выше правилам и формируем новое разбиение.
Если H' = H, то H' представляет собой множество классов эквивалентности.
Первая таблица S для МП-распознавателя (см. табл. 2) представлена в табл. 3.
Таблица 3
Таблица для формирования разбиения
|
|
G1 |
G2 |
G3 |
G4 |
G5 |
|||||||||||
|
1 |
2 |
3 |
4 |
5 |
6 |
8 |
7 |
11 |
13 |
9 |
10 |
12 |
14 |
15 |
16 |
|
|
a |
2 |
2 |
4 |
4 1 |
3 1 |
4 1 |
3 1 |
|
|
|
5 |
5 |
5 |
|
|
|
|
b |
2 |
3 |
2 |
4 1 |
3 1 |
4 1 |
3 1 |
5 |
5 |
5 |
|
|
|
|
|
|
|
˧ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
По этой таблице видно, что подмножество {1,2,3} разбивается на одноэлементные подмножества {1}, {2} и {3}, подмножество {4,5,6,8} – на {4,6} и {5,8}, а остальные подмножества не разбиваются и в результате получаем разбиение {{1}, {2}, {3}, {4,6}, {5,8}, {9,10,12}, {14,15,16}}. По этому разбиению строим новую таблицу S (табл. 4).
Таблица 4
Таблица для формирования разбиения
|
|
G1 |
G2 |
G3 |
G4 |
G5 |
G6 |
G7 |
G8 |
||||||||
|
|
1 |
2 |
3 |
4 |
6 |
5 |
8 |
7 |
11 |
13 |
9 |
10 |
12 |
14 |
15 |
16 |
|
a |
4 |
4 |
7 |
7 2 |
7 2 |
6 3 |
6 3 |
|
|
|
8 |
8 |
8 |
|
|
|
|
b |
5 |
6 |
5 |
7 2 |
7 2 |
6 3 |
6 3 |
8 |
8 |
8 |
|
|
|
|
|
|
|
˧ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
В этой таблице нет различных столбцов, соответствующих символам, принадлежащим какому либо одному подмножеству. Поэтому полученное разбиение является разбиением на классы эквивалентности.
Построение распознавателя с магазинной памятью и меньшим количеством магазинных символов. Используя отношение R на множестве состояний МП-распознавателя М1, можно построить МП-распознаватель М2, эквивалентный распознавателю М1, который будет иметь не больше магазинных символов, чем распознаватель М1. Сокращение количества магазинных символов достигается за счет “стягивания” всех символов, принадлежащих одному классу эквивалентности, в один символ.
МП-распознаватель М2 строим следующим образом.
Возьмем по одному символу из каждого класса эквивалентности, добавим маркер дна и получим множество магазинных символов МП-распознавателя М2.
Возьмем таблицу МП-распознавателя М1 и оставим в ней только те столбцы, которые соответствуют магазинным символам МП-распознавателя М2. Если в клетке полученной таблицы встретится магазинный символ МП-распознавателя М1, который не принадлежит множеству магазинных символов МП-распознавателя М2, то его нужно заменить на эквивалентный ему символ, принадлежащий множеству магазинных символов МП-распознавателя М2.
На множестве магазинных символов МП-распознавателя (см. табл. 2) построено разбиение на классы эквивалентности {{1}, {2}, {3}, {4,6}, {5,8}, {9,10,12}, {14,15,16}}. Из каждого класса выберем символ с меньшим номером и построим таблицу (табл. 5) нового МП-распознавателя по описанным выше правилам. В результате получим МП-распознаватель с меньшим количеством магазинных символов.
Таблица 5
Таблица МП-распознавателя
|
|
1 |
2 |
3 |
4 |
5 |
7 |
9 |
14 |
Ñ |
|
a |
4 ® |
4 ® |
9 ® |
9,2 |
7,3 |
|
14 ® |
|
|
|
b |
5 ® |
7 ® |
5 ® |
9,2 |
7,3 |
14 ® |
|
|
|
|
˧ |
|
|
|
|
|
|
|
|
доп |
Выводы. В статье решена задача преобразования исходного МП-распознавателя в эквивалентный ему распознаватель с меньшим (не большим) количеством магазинных символов. Но задача получения МП-распознавателя с наименьшим количеством магазинных символов, распознающим заданный язык, остается открытой. Для дальнейшего сокращения количества магазинных символов может быть использовано какое либо другое отношение эквивалентности на множестве магазинных символов распознавателя, разбивающее множество символов на меньшее количество классов эквивалентности, такое, что “стягивание” класса эквивалентности в один символ приводит к получению распознавателя, эквивалентного исходному.
1. Schutzenberger M.P. On context-free languages and pushdown automata. Information and Control. 1963. 6:3. P. 246 - 264.
2. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. М.: Мир, 1978. Т. 1, 612 с.
3. Льюис Ф., Розенкранц Д., Стирнз Р. Теоретические основы проектирования компиляторов. М.: Мир, 1979. 656 с.
4. Мартыненко Б.К. Синтаксически управляемая обработка данных. Изд. 2-е, дополн. СПб: Изд-во С.-Петербургского университета, 2004 г. 317 с.
5. Ахо А, Лам М., Сети Р., Ульман Дж. Компиляторы. Принципы, технологии и инструментарий. М: Издательский дом “Вильямс”, 2008. 1185 с.
6. Hopcroft J.E., Motwani R., J.D. Ullman J.D. Introduction to Automata Theory, Languages, and Computation (3rd ed.). Pearson., 2013. p. 496.
7. Рязанов Ю. Д. Синтез распознавателей с магазинной памятью по детерминированным синтаксическим диаграммам // Вестник ВГУ. Системный анализ и информационные технологии. 2014. №1. С. 138 - 145.
8. Рязанов Ю. Д., Савёлова И. Н. Преобразование распознавателя с магазинной памятью и одним состоянием в распознаватель с конечным множеством состояний // Моделирование, оптимизация и информационные технологии. 2015. № 4 (11). С. 13.
9. Рязанов Ю. Д. Преобразование распознавателя с магазинной памятью и конечным множеством состояний в распознаватель с одним состоянием // Вестник БГТУ им. В.Г. Шухова. 2016. № 1. С. 194 - 199.
10. Polyakov V.M., Ryazanov Y.D. Virt Charts to Multiport Component Syntactic Charts Transformation // Global Journal of Pure and Applied Mathematics. 2015. Т. 11. № 5. С. 3939 - 3952.
