Методические указания к курсовой работе по дисциплине «Теория языков программирования и методы трансляции» (стр. 3 из 4)

Рис. 2 Граф переходов детерминированного автомата эквивалентного исходному

Примечание. Чтобы не загромождать рисунок, не изображено состояние Er а также дуги, ведущие в него из других состояний.

Построенный автомат не является минимальным, поэтому необходимо выполнить этап минимизации автомата, на котором строится минимальный (иначе – приведенный) автомат.

6. ПОСТРОЕНИЕ МИНИМАЛЬНОГО АВТОМАТА

Произвольный конечный автомат можно превратить в эквивалентный ему минимальный, выбрасывая недостижимые и объединяя эквивалентные состояния. Разбиение состояний на классы эквивалентности можно осуществить с помощью метода разбиения.

Метод разбиения заключается в разбиении множества состояний на непересекающиеся подмножества или блоки, такие, что неэквивалентные состояния попадают в разные блоки.

Начальное разбиение P0 заключается в разбиении всего множества состояний на подмножества допустимых и недопустимых состояний:

P0=({Y, Y1, Y2, Y3, Y5, Y7, Y9, Y11, Y13, Y14, Y15, Y16, Y18, Y19, Y20, Y22, Y23, Er}, {Y4, Y6, Y8, Y10, Y12, Y17, Y21, Y24})

Далее произведем разбиение блока 1 по входу X5 и получим разбиение

P1=({Y, Y1, Y2, Y9, Y11, Y13, Y14, Y15, Y16, Y18, Y19, Y20, Y22, Y23, Er}, {Y3, Y5, Y7}, {Y4, Y6, Y8, Y10, Y12, Y17, Y21, Y24})

Произведем разбиение блока 1 по входу X0, получим разбиение

P2=({Y, Y1, Y9, Y11, Y13, Y14, Y15, Y18, Y19, Y22, Er}, {Y16, Y20, Y23}, {Y2}, {Y3, Y5, Y7}, {Y4, Y6, Y8, Y10, Y12, Y17, Y21, Y24})

Произведем разбиение блока 1 по входу X7, получим разбиение

P3=({Y1, Y9, Y11, Y13, Y14, Y15, Y18, Y19, Er}, {Y}, {Y22}, {Y16, Y20, Y23}, {Y2}, {Y3, Y5, Y7}, {Y4, Y6, Y8, Y10, Y12, Y17, Y21, Y24})

Произведем разбиение блока 1 по входу X6, получим разбиение

P4=({Y9, Y11, Y13, Y14, Y15, Y18, Y19, Er}, {Y1}, {Y}, {Y22}, {Y16, Y20, Y23}, {Y2}, {Y3, Y5, Y7}, {Y4, Y6, Y8, Y10, Y12, Y17, Y21, Y24})

Произведем разбиение блока 1 по входу X3, получим разбиение

P5=({Y13, Y14, Y15, Y18, Y19, Er}, {Y9, Y11}, {Y1}, {Y}, {Y22}, {Y16, Y20, Y23}, {Y2}, {Y3, Y5, Y7}, {Y4, Y6, Y8, Y10, Y12, Y17, Y21, Y24})

Произведем разбиение блока 1 по входу X4, получим разбиение

P6=({Y13, Y14, Y18, Er}, {Y15, Y19}, {Y9, Y11}, {Y1}, {Y}, {Y22}, {Y16, Y20, Y23}, {Y2}, {Y3, Y5, Y7}, {Y4, Y6, Y8, Y10, Y12, Y17, Y21, Y24})

Произведем разбиение блока 1 по входу X2, получим разбиение

P7=({Y14, Y18, Er}, {Y13}, {Y15, Y19}, {Y9, Y11}, {Y1}, {Y}, {Y22}, {Y16, Y20, Y23}, {Y2}, {Y3, Y5, Y7}, {Y4, Y6, Y8, Y10, Y12, Y17, Y21, Y24})

Произведем разбиение блока 1 по входу X5, получим разбиение

P8=({Er}, {Y14, Y18}, {Y13}, {Y15, Y19}, {Y9, Y11}, {Y1}, {Y}, {Y22}, {Y16, Y20, Y23}, {Y2}, {Y3, Y5, Y7}, {Y4, Y6, Y8, Y10, Y12, Y17, Y21, Y24})

Множество Р8 не допускает дальнейшего разбиения ни по одному входу, оно содержит подмножества (блоки) эквивалентных состояний, которые и являются состояниями минимального автомата.

Введем обозначения для этих подмножеств – состояний минимального автомата (табл. 7).

Таблица 7

Состояния минимального автомата

Блок эквивалентных состояний	Состояние минимального автомата
{Y}	1
{Y1}	2
{Y2}	3
{Y3, Y5, Y7}	4
{Y9, Y11}	5
{Y13}	6
{Y14, Y18}	7
{Y15, Y19}	8
{Y16, Y20, Y23}	9
{Y22}	10
{Y4, Y6, Y8, Y10, Y12, Y17, Y21, Y24}	11
{Er}	Er

Таблица переходов минимального автомата показана в табл. 8.

Таблица8

Таблица переходов минимального автомата

	x0	x2	x3	x4	x5	x6	x7
1	Er	Er	Er	Er	2	6	4	0
2	Er	Er	Er	Er	Er	3	Er	0
3	4	Er	Er	4	Er	Er	Er	0
4	Er	5	Er	Er	11	Er	Er	0
5	Er	1	11	Er	Er	Er	Er	0
6	Er	10	Er	Er	7	Er	7	0
7	Er	Er	Er	Er	8	Er	Er	0
8	Er	Er	Er	9	Er	Er	Er	0
9	11	Er	Er	Er	Er	Er	Er	0
10	Er	Er	Er	Er	Er	Er	9	0
11	Er	Er	Er	Er	Er	Er	Er	1
Er	Er	Er	Er	Er	Er	Er	Er	0

Граф переходов минимального автомата, построенный по табл. 8, показан на рис. 3.

Рис. 3. Граф переходов минимального распознающего автомата

Примечание. Чтобы не загромождать рисунок, не изображено состояние Er, а также дуги, ведущие в него из других состояний.

7. ИСПОЛЬЗОВАНИЕ СЕТЕЙ ПЕТРИ ПРИ ПЕРЕХОДЕ ОТ ГРАММАТИКИ К МИНИМАЛЬНОМУ АВТОМАТУ

Построим для грамматики G' сеть Петри. Это можно сделать, поставив в соответствие нетерминальным символам позиции (кружки) сети, а терминалам – переходы (планки) сети. Будем помечать позиции и переходы соответствующими нетерминалами и терминалами. Поскольку сеть Петри является двудольным графом, соединение дугами позиций разрешается только через переходы, а переходов - через позиции. Если в правой части некоторого правила вывода из R' имеет место конкатенация терминалов, то в сети Петри между переходами, помеченными терминалами, должны появляться дополнительные позиции, которые можно помечать символами левой части правила вывода с верхними индексами 1, 2, ... . Так, фрагмент сети Петри, соответствующий первому правилу вывода (S ® x5 x6 x0 A) , будет иметь вид, показанный на рис. 4. При построении остальных фрагментов, соответствующих последующим правилам вывода, следует использовать ранее обозначенные позиции (но не переходы!). Таким образом, позиции могут иметь несколько входящих и исходящих дуг, но переходы – в точности по одной входящей и не более чем одной исходящей дуге (исходящая дуга может отсутствовать, если в правой части правила вывода отсутствует замыкающий нетерминал).

Рис. 4. Фрагмент интерпретированной сети Петри, соответствующий правилу вывода S ® x5 x6 x0 A

Маркером отмечается позиция, соответствующая начальному символу грамматики G' (в данном случае это позиция S).

В остальном правила построения сети Петри ясны из рассматриваемого сквозного примера - сравнить правила R' с рис. 5.

Рис. 5. Сеть Петри, соответствующая исходной грамматике

Понятно, что сеть на рис. 5 представляет собой ни что иное, как автоматную сеть Петри (подкласс сетей Петри) и что позиции можно трактовать как состояния конечного автомата, а переходы - как входные символы.

Для полноты соответствия построенной сети Петри распознающему автомату Мура введем не показанную на рис. 5 заключительную позицию Z, в которую направим дуги из всех переходов, ранее не имевших исходящих дуг (см. рис. 6).

Рис 6. Сеть Петри, дополненная заключительной позицией Z.

Теперь следует заметить, что в сети на рис. 6 имеются три идентичных фрагмента, содержащие позиции A, B и C, каждой из которых инцидентны по два выходных перехода x2 и x5, и еще два идентичных фрагмента с позициями D и E, каждой из которых инцидентен выходной переход x3.

Функционирование сети не изменится, если склеить идентичные фрагменты. Позиции S1 и S3; F1 и F4; F2 и F5; F3, F6 и F8 также можно склеить (см. рис. 7).

Рис. 7. Преобразованная недетерминированная сеть Петри

Этот этап соответствует минимизации числа состояний автомата, но он выполнен для автомата, сохраняющего недетерминированность. Источником недетерминированности, очевидно, могут являться лишь позиции свободного выбора, исходящие дуги которых являются входящими дугами переходов, помеченных одинаковыми терминалами. В данном случае к таким позициям следует отнести лишь позицию (S1, S3). Способ устранения недетерминированности виден из рисунка 9.