Синтез конечного распознающего автомата

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

ДИПЛОМНЫЙ ПРОЕКТ

по дисциплине «Теория вычислительных процессов и структур»

СИНТЕЗ КОНЕЧНОГО РАСПОЗНАЮЩЕГО АВТОМАТА

СОДЕРЖАНИЕ

• Введение
• 1.Построение праволинейной грамматики
• 2.Построение автоматной грамматики по праволинейной
• 3.Построение недетерминированного конечного автомата
• 4.Преобразование недетерминированного конечного автомата в детерминированный
• 5.Минимизация числа состояний автомата
• 6.Программная реализация конечного автомата
• 7.Использование сетей Петри при переходе от грамматики к минимальному автомату
• 8.Размещение состояний автомата
• 9.Структурный синтез автомата
• 10.Реализация автомата
• Заключение
• Список использованной литературы
• ВВЕДЕНИЕ
• Синтез конечных автоматов является важным разделом в изучении вопросов организации вычислительных процессов и структур. Необходимость в построении теории автоматов возникла с развитием вычислительной техники, с появлением теории формальных языков и грамматик - теории, позволяющей описывать и анализировать синтаксические свойства языков программирования и других формальных языков. Потребовалось решение вопросов преобразования грамматик в автоматы, которые бы распознавали и транслировали множества, задаваемые грамматиками.
• Основой изучения данного раздела теории является
• · построение базовых формальных моделей описания логических
• структур, динамики поведения вычислительных структур;
• · выработка навыков проектирования вычислительных систем;
• · формирование представления о методах, используемых при решении задач анализа, синтеза организации функционирования вычислительных структур и системного программного обеспечения.
• 1. ПОСТРОЕНИЕ ПРАВОЛИНЕЙНОЙ ГРАММАТИКИ
• Исходными данными для дипломного проекта являются две таблицы (табл.1, табл.2) и правила вывода R.
• Табл.1 состоит из трех строк, первая из которых содержит перечисление 18 символов Ci. Во вторую строку Si записываются первые 18 символов фамилии, имени и отчества студента с обязательными пробелами между фамилией именем и отчеством. В третью строку для каждой из 18 букв строки Si заносится символ из алфавита {x₀,x₁,x₂,x₃,x₄,x₅,x₆,x₇} в соответствии с табл.2.
• Таблица 1

Ci

C1

C2

C3

C4

C5

C6

C7

C8

C9

C10

C11

C12

C13

C14

C15

C16

C17

C18

Si

П

А

С

Е

Ц

К

И

Й

И

Л

Ь

Я

А

Н

Д

Р

Xi

X5

X1

X4

X6

X1

X7

X3

X0

X5

X3

X0

X6

X7

X5

X1

X7

X6

X0

• Табл.2 построена на основе подсчета появлений каждой буквы русского алфавита в фамилиях, именах и отчествах. Затем буквы сформированы в восемь групп с таким расчетом, чтобы появление каждого из символов x₀-x₇ было равновероятным.
• Таблица 2

А

Б

В

Г

Д

Е

Ж

3

И

Й

К

Л

М

Н

О

П

x1

x5

x2

x4

x6

x6

x4

x3

x3

х0

x7

х0

x3

x7

x4

x5

Р

С

Т

У

Ф

X

Ц

Ч

Ш

Щ

Ь

Ы

Э

Ю

Я

хо

x4

x5

x7

x2

x5

x1

x2

x2

хо

x6

x1

x1

x3

x7

x5

• Грамматикой G[S] называется непустое множество правил вывода (продукционных правил), где S - начальный символ.
• Правило вывода (продукция) представляет собой упорядоченную пару (R,х) и записывается в виде R::=х, где: R - левая часть правила (в данном случае символ); x - непустая цепочка, образующая правую часть правила.
• Грамматика задается на алфавите V, называемым словарем. Алфавит V это непустое множество элементов (символов). В свою очередь, цепочка х представляет некоторую последовательность символов алфавита V (возможно повторяющихся). Число входящих в цепочку символов называют длиной цепочки.
• Словарь состоит из двух непересекающихся подмножеств: V_n - словарь нетерминальных символов; V_t - словарь терминальных символов. Таким образом, формальная грамматика G есть четверка G=(V_N,V_t,S,R), причем SV_n.
• Продукция (правило вывода) называется линейной, если как в правой, так и в левой части продукции используется не более одного нетерминального символа. Продукция называется праволинейной, если нетерминал находится справа от всех символов правой части правила. Аналогично, если нетерминал находится левее всех других символов правой части, продукция называется леволинейной. Грамматика также называется праволинейной или леволинейной, если каждая из ее продукций является соответственно праволинейной или леволинейной.
• Для рассматриваемой в работе грамматики
• G=(V_n,V_t,S,R)
• V_n={S,A,B,C,D,E,F}; V_t={C₁,C₂,С₃, ..., C₁₈};
• R - множество продукций (правил вывода):
• Sc₁c₂c₃A; Sc₁c₄c₅B; Sc₆С; Sс₇F; Ac₈D; Ac₉; Bc₈E; Bc₉;
• Cc₈E; Cc₉; Dc₁₀S; Dc₁₁; Ec₁₀S; Eс₁₁; Fc₁₂c₁₃c₁₄c₁₅;
• Fc₁₆c₁₃c₁₄c₁₅; Fс₁₇ c₁₈ c₁₅.
• Анализ продукций данной грамматики показывает, что все они праволинейны, следовательно, грамматика будет праволинейной.
• Приведем грамматику к виду
• G'=(V_n,V'_t,S,R'), где
• V'_t = {x_o,x₁, ..., x₇} - новый терминальный словарь;
• R' - множество правил вывода, получаемых заменой символов из словаря V_t, на символы из словаря V_т в соответствии с табл1.
• В рассматриваемом примере эти правила имеют вид
• S X₅ X₁ X₄ A | X₅ X₆ X₁ B | X₇ C | X₃ F
• A X₀ D | X₅
• B X₀ E | X₅
• C X₀ D | X₅
• D X₃ S | X₀
• E X₃ S | X₀
• F X₆ X₇ X₅ X₁ | X₇ X₇ X₅ X₁ | X₆ X₀ X₁
• здесь “ | ” это металингвистический символ «или».
• Примерами цепочек, которые принадлежат языку L(G'), порождаемому грамматикой G', являются (x₅x₁x₄x₅, x₇x₀x₀, x₃x₆x₀x₁). В то же время, цепочки (x₅х₅х₆x₁х₅, х₄x₆x₀x₁) не принадлежат языку L(G'), так как их нельзя вывести в грамматике G'. Языком L грамматики G(S) называется множество всех предложений L(Y), где Y - предложение. Предложением называется состоящая из терминальных символов сентенциальная форма Y. Сентенциальной формой называется цепочка Y, выводимая из начального символа S', грамматики G(S'),что можно записать как S=>*Y, где =>* это рефлексивное транзитивное замыкание отношения простого вывода.
• 2. ПОСТРОЕНИЕ АВТОМАТНОЙ ГРАММАТИКИ ПО ПРАВОЛИНЕЙНОЙ
• Автоматные грамматики, или иначе А-грамматики, имеют правила вывода вида
• U::=T или U::=TW, где TV_T; UV_n; WV_n.
• Перейти от полученной праволинейной грамматики к автоматной можно расширением нетерминального словаря следующим образом: Sc₁S₁; S₁c₂S₂; S₂с₃А и т.д, оставляя в правой части правила один терминальный и один нетерминальный символы или один терминальный.
• Для рассматриваемого примера выполним преобразование праволинейной грамматики G'=(V_N,V_T,S,R') в автоматную G"=(V_N",V_T,S,R").
• При этом получим следующее множества R правил вывода

Sx5S1;	S1x1S2;	S2x4A;
Sx5S3;	S3x6S4;	S4x1B;
Sx7C;	Sx3F;	Ax0D;
Ax5;	Bx0E;	Bx5;
Cx0E;	Cx5;	Dx3S;
Dx0;	Ex3S;	Ex0;
Fx6F1;	F1x7F2;	F2x5F3;
F3x1;	Fx7F4;	F4x7F5;
F5x5F6;	F6x1;	Fx6F7.
F7x0F8;	F8x1;

• Следовательно, словарь нетерминальных символов V_N будет иметь вид
• V"_N = {S,S₁,S₂,S₃,S₄,А,В,С,D,E,F,F₁,F₂,F₃,F₄,F₅,F₆,F₇,F₈}.
• В рассматриваемом примере нетерминальный словарь имеет 19 символов и его мощность V"_N равна 19, мощность V_T терминального словаря V_T равна 8.
• 3. ПОСТРОЕНИЕ НЕДЕТЕРМИНИРОВАННОГО КОНЕЧНОГО АВТОМАТА
• Недетерминированный конечный автомат это пятерка A=(Q,V,М,S,Z), где Q - множество (алфавит) внутренних состояний; V - входной алфавит;
• М - функция переходов, представляющая отображение V*QP(Q);
• P(Q) - множество подмножеств из Q; SQ - множество начальных состояний; ZQ - множество заключительных состояний; SZ.
• Недетерминированный конечный автомат (в отличие от детерминированного) может иметь несколько начальных состояний. Отличается он и функциями перехода.
• Как правило, недетерминированные конечные автоматы порождаются регулярными грамматиками, которые содержат правила вывода вида
• U::= TWR::= TW, что соответствует фрагменту диаграммы
• Частичная функция переходов этого случая имеет вид: M(W,T)={U,R}.
• В рассматриваемом примере недетерминированный конечный автомат имеет одно начальное состояние S. Зададим этот автомат следующим образом. Поставим в соответствие символам нетерминального словаря V"_N состояния из Q, в том числе нетерминалу S - начальное состояние q_o. Добавим заключительное состояние Z, в котором автомат оказывается, если цепочка символов, поступающих на автомат, принадлежит L (G").
• Составим табл.3, в которой, нетерминальным символам из множества V"_N соответствуют состояния автомата из множества Q.
• Таблица 3

S	S1	S2	S3	S4	A	B	C	D	E
q0	q1	q2	q3	q4	q5	q6	q7	q8	q9
F	F1	F2	F3	F4	F5	F6	F7	F8	Z
q10	q11	q12	q13	q14	q15	q16	q17	q18	q19

• Здесь начальному состоянию S соответствует q_o, а конечному Z соответствует q₁₉. Общее количество состояний Q=V"_N+1 и равно 20.
• Поставим в соответствие правилам вывода переходы автомата. Так, правилу Аx₀D - переход из состояния q₅ в состояние q₈ под воздействием входного символа x₀, а правилу Ех₀ - переход из состояния q₉ в заключительное состояние q₁₉ при входном символе х₀.
• Выполнив указанные действия для всех правил R", получим таблицу переходов (табл.4) недетерминированного конечного автомата, соответствующего рассматриваемому примеру. Граф переходов, построенный по этой таблице, приведен на рис.1.
• Таблица 4

	X0	X1	X2	X3	X4	X5	X6	X7
q0				q10		q1,3		q7
q1		q2
q2					q5
q3							q4
q4		q6
q5	q8					q19
q6	q9					q19
q7	q9					q19
q8	q19			q0
q9	q19			q0
q10							q11,17	q14
q11								q12
q12						q13
q13		q19
q14								q15
q15						q16
q16		q19
q17	q18
q18		q19
q19

• Рис.1
• В полученном графе присутствуют девять цепочек переходов по графу: 51400; 5145; 5615; 56100; 700; 75; 36751; 37751; 3601; и три цепочки: 51403; 56103; 703; при которых происходит возвращение к начальному состоянию автомата S = q₀.
• Анализируя полученный граф переходов, можно убедиться, что автомат допускает те и только те цепочки входных символов, которые принадлежат языку L(G"), порождаемому грамматикой G".
• Кроме того, полученный автомат является недетерминированным, так как в табл.4 есть клетки, содержащие пары состояний, и не полностью определённым, поскольку в таблице есть незаполненные клетки.
• 4. ПРЕОБРАЗОВАНИЕ НЕДЕТЕРМИНИРОВАННОГО КОНЕЧНОГО АВТОМАТА В ДЕТЕРМИНИРОВАННЫЙ
• Детерминированный конечный автомат это пятерка А=(Q,V,М,S,Z), где Q - алфавит состояний; V - входной алфавит; М - функция переходов (Q*VР(Q)); S - начальное состояние; Z - множество заключительных состояний; SZ.
• В этом автомате, в отличие от недетерминированного, всегда одно начальное состояние, а также отсутствуют альтернативные состояния, в которые переходит автомат при подаче на вход одного и того же входного символа.
• В рассматриваемом примере такими состояниями являются q₁ и q₃, в которые переходит автомат из состояния q_o под воздействием х₅.
• Преобразование недетерминированного конечного автомата в детерминированный основано на замене альтернативных состояний одним, эквивалентным этим состояниям, например:
• Здесь три альтернативных состояния X,Y,Z в недетерминированном конечном автомате представляются одним [XYZ] в детерминированном, которое представляет первые три состояния. Следовательно, если недетерминированный конечный автомат представляют пятеркой А=(Q,V_T,M,S,Z), то эквивалентный детерминированный конечный автомат имеет вид А=(Q,V_T,М',S,Z).
• Алфавит состояний Q' определяется через подмножество алфавита Q.
• Функция переходов М определяется как M([q₁,q₂,…,q_k],T)= [R₁,R₂,…,R_t], если в недетерминированном конечном автомате M({q₁,q₂,...,q_k},T) = {R₁,R₂,...,R_t}.
• Начальное состояние S'=[S₁,S₂,...,S_i]=q_0, еcли S={S₁,S₂,...,S_i}.
• Множество заключительных состояний Z' образуется из элементов, в которых присутствует хотя бы одно состояние из множества Z недетерминированного конечного автомата.
• Построенный по этим правилам эквивалентный детерминированный конечный автомат допускает одни и те же входные цепочки, что и исходный недетерминированный.
• Рис.2
• В рассматриваемом примере недетерминированность автомата локально проявляется в том, что из некоторого его состояния q_i исходят несколько дуг, помеченных одним и тем же символом х_j (рис.2).
• Недетерминированность в этом случае может быть легко устранена «склеиванием» двух состояний q₁ и q_k в одно q_1,k . При этом q_{1, k} инцидентны все исходящие дуги х_г, х_р, x_t, являющиеся исходящими дугами состояний q₁ и q_k (рис.3).
• Рис.3
• Общий алгоритм нахождения детерминированного конечного автомата, эквивалентного недетерминированному, может быть описан следующим образом:
• Построить начальное состояние S' и отметить им первую строку таблицы переходов.
• Определить все состояния Q', которые могут быть достигнуты из данного состояния.
• Если во вновь определенных состояниях не встречаются такие, которые отмечали ранее строки таблицы, то для них надо выделить новые строки и повторить п.2.
• В таблице переходов выделить заключительные состояния Z'.
• Таблица 5

	X0	X1	X2	X3	X4	X5	X6	X7
q0				q10		q1,3		q7
q1,3		q2					q4
q2					q5
q4		q6
q5	q8					q19
q6	q9					q19
q7	q9					q19
q8	q19			q0
q9	q19			q0
q10							q11,17	q14
q11,17	q18							q12
q12						q13
q13		q19
q14								q15
q15						q16
q16		q19
q18		q19
q19

• В результате применения этого алгоритма от автомата, орграф которого представлен на рис.1, можно перейти к эквивалентному детерминированному автомату, таблица переходов которого приведена в табл.5, а орграф на рис.4.
• Из рис.1 нетрудно видеть, что в рассматриваемом примере «источниками недетерминированности» является всего два состояния - q₀ и q₁₀. Очевидно, что если «склеить» пару состояний {q₁ и q₃} и пару состояний {q₁₁ и q₁₇} образовав новые состояния q_1,3 и q_11,17, то недетерминированность устраняется.
• Орграф на рис.4 задает все допустимые последовательности входных символов, которые соответствуют всем цепочкам терминалов, выводимых в данной грамматике.
• Очевидно, что для определения с помощью распознающего автомата запрещенных последовательностей входных символов (невыводимых цепочек) орграф следует дополнить состоянием q₂₀ «Ошибка», в которое должны вести дуги, исходящие из всех остальных состояний автомата (в том числе и заключительного). Эти дуги должны быть помечены дизъюнкциями входных символов, отличных от символов, помечающих дуги, выходящие из данного состояния, или инверсией дизъюнкции этих символов, например, для состояния q_1,3 в состояние q₂₀ должна вести дуга, помеченная дизъюнкцией x₀ v x₂ v x₃ v x₄ v x₅ v x₆, или, иначе, (в силу ортогональности входных символов).
• В орграфе (рис.4) этого не сделано, чтобы не усложнять картину, однако в табл.5 состояние q₂₀ «Ошибка» введено (последняя строка), и можно считать, что во все ее пустые клетки вписано состояние q₂₀. В этом случае табл.5 задает полностью определенный детерминированный конечный автомат.
• Рис.4
• Анализируя полученный граф, можно выявить девять цепочек переходов по графу: 51400; 5145; 5615; 56100; 700; 75; 36751; 3601; 37751; и три цепочки: 51403; 56103; 703; при которых происходит возвращение к начальному состоянию автомата S = q₀.
• МИНИМИЗАЦИЯ ЧИСЛА СОСТОЯНИЙ АВТОМАТА
• Минимизация автомата, эквивалентного полученному в предыдущем разделе полностью определенному автомату, проводится в два этапа. Сначала множество состояний автомата разбивается на классы эквивалентности, а затем строится минимальный (приведенный) автомат.
• Рассмотрим алгоритм приведения автомата для случая модели Мура, к которой относится рассматриваемый пример.
• Построим треугольную таблицу (табл.6), клетки которой соответствуют всем парам рабочих состояний (q_i,q_j) ij, т.е. состояний, отличных от q₂₀ «Ошибка». Если для рабочих состояний q_i и q_j в табл.5 существует входной символ х₁, при котором переход из q_i осуществляется в одно из рабочих состояний, а из q_j в состояние ошибки, то состояние q_i и q_j не эквивалентны, и соответствующая им клетка помечается крестом. То есть, если какие - либо две строчки табл.5 содержат разное число рабочих состояний или отличаются позициями, занимаемыми рабочими состояниями, то обозначающие эти строки состояния не эквивалентны. В противном случае в клетку табл.6 с координатами q_i, q_j запишем каждую пару состояний (q_s,q_t), ts, в которые автомат может перейти из q_i и q_j при подаче одного и того же входного символа (количество этих пар равно числу столбцов с рабочими состояниями в строке q_i и q_j табл.5).
• В рассматриваемом случае в табл.5 автомат из состояния q_o переходит в рабочие состояния при входных символах х₃, х₅, х₇, при остальных входных символах, q_o переходит в состояние q₂₀ «Ошибка». Других состояний, которые оказываются в рабочих состояниях при том же наборе входных символов (х₃, х₅, х₇) нет, поэтому в столбце q_o табл.6 все клетки следует вычеркнуть. То же можно сделать со столбцами q_1,3, q_2. Из состояния q₄ автомат переходит в состояния q₆ при входном символе х₁, и при этих же символах в рабочие состояния автомат переходит из состояний q₁₃, q₁₆, q₁₈, поэтому три клетки в столбце q₄ не должны вычеркиваться. Проделав эту операцию со всеми столбцами, теперь необходимо определить явность эквивалентности пар состояний. Для этого берем не вычеркнутые клетки в табл.5, например {q₄ и q₁₃} и проверяем на рис.4 эти два состояния. Если оба состояния переходят при одинаковом x_i, в одно и то же состояние q_i, то пары состояний явно эквиваленты. В нашем примере, пары {q₄ и q₁₃} переходят при одинаковом x₁, но в разные состояния (q₄ в q₆, а q₁₃ в q₁₉), следовательно пара состояний не эквивалента и клетку необходимо вычеркнуть. А пара состояний {q₁₃ и q₁₆} будет эквивалента, т.к. переход осуществляется по x₁ в состояние q₁₉ как из q₁₃, так и из q₁₆.
• Таблица 6

0

1,3

X

2

X

X

4

X

X

X

5

X

X

X

X

6

X

X

X

X

7

X

X

X

X

8

X

X

X

X

X

X

X

9

X

X

X

X

X

X

X

10

X

X

X

X

X

X

X

X

X

11,17

X

X

X

X

X

X

X

X

X

X

12

X

X

X

X

X

X

X

X

X

X

X

13

X

X

X

+

X

X

X

X

X

X

X

X

14

X

X

X

X

X

X

X

X

X

X

X

X

X

15

X

X

X

X

X

X

X

X

X

X

X

X

X

16

X

X

X

+

X

X

X

X

X

X

X

X

X

X

18

X

X

X

+

X

X

X

X

X

X

X

X

X

X

19

X

X

X

X

X

X

X

X

X

X

X

X

X

X

X

X

X

0

1,3

2

4

5

6

7

8

9

10

11,17

12

13

14

15

16

18

19

• Не вычеркнутые клетки результирующей таблицы соответствуют всем парам эквивалентных состояний.
• Класс эквивалентности образуется состояниями, которые попарно эквивалентны. В данном случае образуются следующие пары эквивалентных состояний:
• {q₅ и q₆} {q₅ и q₇} {q₆ и q₇} {q₈ и q₉} {q₁₂ и q₁₅} {q₁₃ и q₁₆} {q₁₃ и q₁₈} {q₁₆ и q₁₈}.
• Всего восемь пар попарно эквивалентных состояний. Эти состояния образуют пять классов эквивалентности: {q₅, q₆, q₇}, {q₈, q₉}, {q₁₂ , q₁₅}, {q₁₃, q₁₆ , q₁₈}.
• Каждое состояние, не вошедшее ни в один класс эквивалентности, эквивалентно лишь само себе и само образует этот класс. В рассматриваемом примере к нерасчлененным пяти классам необходимо добавить еще семь классов эквивалентности: q₀; q_1,3; q₂; q₄; q_11,17; q₁₄; q₁₉.
• Состояние минимального автомата обозначим буквами r с индексами
• r₀ = {q₀}; r₁={q_1,3}; r₂={q₂}; r3={q₄}; r4={q₅, q₆, q₇}; r₅={q₈, q₉}; r₆={q₁₀};
• r₇={q_11,17}; r₈={q₁₂, q₁₅}; r₉={q₁₃, q₁₆, q₁₈}; r₁₀={q₁₄}; r₁₁={q₁₉}.
• Таким образом, минимальный автомат содержит 12 состояний, не считая состояния r₁₂⁼{q₂₀} "Ошибка". Орграф этого автомата приводится на рис.5 (без указания состояния «Ошибка»), а таблица переходов в табл.7.

• Рис.5
• Проанализировав полученный граф, можно выявить девять цепочек переходов по графу: 51400; 5145; 56100; 5615; 700; 75; 3501; 36751; 37751; и три цепочки: 51403; 56103l; 703; при которых происходит возвращение к начальному состоянию автомата S = r₀.
• В этой таблице, также как и в табл. 5, незаполненные клетки соответствуют состоянию «Ошибка».
• Таблица 7

	X0	X1	X2	X3	X4	X5	X6	X7
r0				r6		r1		r4
r1			r2				r3
r2					r4
r3		r4
r4	r5					r11
r5	r11			r0
r6							r7	r10
r7	r9							r8
r8						r9
r9		r11
r10								r8
r11

• ПРОГРАММНАЯ РЕАЛИЗАЦИЯ КОНЕЧНОГО АВТОМАТА

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

Рис.6. Пример распознанной цепочки



Рис.7. Пример нераспознанной цепочки

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

Для построения сети Петри рассмотрим полученную во втором пункте дипломной работы праволинейную грамматику G”. Это можно сделать, если поставить в соответствие нетерминальным символам места в сети, а терминальным символам - переходы сети. Обозначим места кружками, а переходы - прямоугольниками (полочками). Будем помечать места и переходы соответствующими терминальными и нетерминальными символами. Поскольку сеть Петри - двудольный граф, соединение дугами мест разрешается только через переходы, а переходов - через места.

Если в правой части некоторого правила вывода из R имеет место катенация терминалов, то в сети Петри между переходами, помеченными терминалами, появляются дополнительные позиции. Эти позиции помечаются символами левой части правила вывода с верхними индексами 1,2,…. Поэтому фрагмент сети Петри, соответствующий первому правилу вывода (Sx₅,x₁,x₄,A), будет иметь следующий вид (рис.8).



Рис.8

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

Построим по полученным правилам вывода R' сеть Петри (рис.9).

Рис.9

Построенная сеть представляет собой автоматную сеть Петри, и места можно трактовать как состояния конечного автомата, а переходы - как входные символы. Чтобы обеспечить полное соответствие построенной сети Петри автомату Мура, необходимо ввести не показанную на рис.9 заключительную позицию Z, в которую можно направить дуги из переходов, не имеющих исходящих дуг.

Если теперь рассмотреть отдельные фрагменты сети на рис.9, то нетрудно заметить одинаковые фрагменты: места А,В,С с одинаковыми инцидентными им переходами x₀ и x₅, а также еще два идентичных фрагмента с местами D и Е, каждому из которых инцидентны по два выходных перехода x₃ и x₀. Аналогично можно отметить места F1 и F7, F2 и F5, а также F3, F6 и F8. В то же время места S1 и S3 идентичны по входу, т.е. из места S в места S1 и S3 дуги идут через переходы x₅.

Функционирование сети не изменится, если «склеить» идентичные фрагменты, что будет соответствовать минимизации числа состояний автомата. Источником недетерминированности могут быть места, из которых исходят дуги, являющиеся входящими дугами переходов, помеченных одинаковыми терминалами. В данном случае таким местом является начальное состояние S и переходы x₅. Таким образом, производится устранение недетерминированности. В результате получим сеть Петри с минимальным числом мест (рис.10).

Можно также установить взаимно-однозначное соответствие между сетью на рис.10 и исходным орграфом.

Для этого местам сети ставятся в соответствие состояния автомата, а переходам - пометки на дугах.



Рис.10

РАЗМЕЩЕНИЕ СОСТОЯНИЙ АВТОМАТА

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

Для асинхронного автомата необходимо применять противогоночное кодирование с целью устранения сбоев. Синхронный автомат не требует противогоночного размещения, и его состояния могут быть закодированы кодами минимальной длины. Поэтому будем рассматривать реализацию синхронного автомата.

Длина кода измеряется числом двоичных переменных, набор значений которых образует кодовую комбинацию из нулей и единиц. Наименьшее число переменных, необходимое для кодирования синхронного автомата с N состояниями, определяется как n=log₂N, где K - ближайшее сверху к К целое число. Для рассматриваемого примера N=12(r₀?r_n) и n=log₂12=4.

Один из способов кодирования состояний синхронного автомата состоит в произвольном назначении кодовых наборов. Рассмотрим данное кодирование для нашего случая.

Состоянию r_i необходимо поставить в соответствие одну из вершин 4-мерного куба с десятичным номером i, который определяется по значениям двоичных координат z₁, z₂, z₃ и z₄ этой вершины в соответствии с формулой

i= z₁2⁰+ z₂2¹+ z₃2²+ z₄2³.

В этом случае вершине с координатами 0000 соответствует состояние r₀, вершине с координатами 0001 - r₁ и так далее (рис.11). Всего в рассматриваемом случае 12 состояний, поэтому 4 вершины куба из 16 остаются неиспользованными. При таком варианте кодирования переход автомата из одного состояния в другое в общем случае может сопровождаться изменениями значений нескольких переменных. Так, при переходе r₄ - r₁₁ (0100-1011), возникающем при входном сигнале x₅, изменяют свои значения все четыре внутренних кодирующих переменных z₁ ? z₄.

Число внутренних переменных, которые изменяют свои значения при переходе автомата из одного состояния в другое, есть расстояние по Хемменгу между этими состояниями.

Очевидно, что чем меньше внутренние переменные изменяются при каждом переходе автомата, тем меньше единиц содержат их переключательные функции. В силу этого выбор варианта кодирования состояний автомата может выполнятся в соответствии с критерием минимальности по Хемменгу по всем переходам. Суть такого кодирования заключается в максимально возможном использовании соседних кодовых состояний, что обычно делается при противогоночном кодировании асинхронных автоматов. Кодовые состояния называются соседними, если при переходе автомата из одного состояния в другое изменяет свое значение лишь одна кодирующая переменная (расстояние по Хеммингу равно 1).

Известно, что такой способ кодирования избыточен и может потребовать (2log₂N - 1) кодирующих переменных при N состояниях автомата. В рассматриваемом случае используется код минимальной длины, n=log₂N, поэтому на некотором шаге кодирования может оказаться, что все соседние коды уже заняты, что потребует увеличения расстояния по Хеммингу на следующем шаге кодирования.

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

На рис.12 приведен один из возможных вариантов размещения, где состояние «Ошибка» (r₁₂) не показано, т.к. оно не удовлетворяет принятому критерию размещения из-за того, что в это состояние производятся переходы из всех других состояний, поэтому кодирование состояния «Ошибка» выполняется позднее.

Размещение начнем с состояния r₄ (как имеющего наибольшее количество входящих и исходящих дуг), которое поместим в вершину 0000 куба. Состояние r₁₁, связанное дугой x₅ с состоянием r₄, поместим в вершину 0010, удаленную от r₄ на расстоянии 1. В вершинах 0100 и 0001разместим состояния r₂ и r₃, также удаленные от r₄ на расстояние 1. Пометим соответствующие этим переходам дуги символами x₄ и x₁. Естественным будет также размещение состояния r₅ в вершине 0011, это состояние связано дугами x₃ и x₀ с состояниями r₀ и r₁₁, причем эти дуги расположены на ребрах куба и имеют минимальную длину, равную 1. Расстояния, соответствующие переходам r₀ - r₄ (по дуге x₇) и r₄-r₅ (по дуге x₅), имеют соответственно длину 3 и 2.



Рис.11

Рис.12

Состояние r₀ связано дугой x₃ с состоянием r₆. Разместим состояние r₆ в вершине 1111, отстоящей от r₀ также на расстояние 1. Продолжая операцию размещения состояний исходного орграфа, получим окончательно картинку, представленную на рис.12.

Проанализируем полученное размещение. Из 18 возможных переходов 14 являются соседними и имеют расстояние 1, три перехода имеют расстояние 2 и один 3. Общее суммарное расстояние 23. Возможны и другие варианты размещения состояний автомата с той же величиной суммарного расстояния по Хеммингу, однако существенного значения это не имеет.

СТРУКТУРНЫЙ СИНТЕЗ АВТОМАТА

Для выбранной синхронной модели автомата применим структурную схему, приведенную на рис.13.

Рис.13

Эта схема состоит из дешифратора входных сигналов, комбинационной схемы, которая реализует функции возбуждения элементов памяти и самой памяти, построенной из триггеров на двухрегистровой основе. В синхронных автоматах отсутствует необходимость бороться с функциональными и логическими состязаниями в дешифраторе и комбинационной схеме, так как предполагается, что все переходные процессы в этих схемах успевают закончиться к моменту появления первого синхросигнала t₁, по которому информация с выходов комбинационной схемы записывается в триггеры регистра 1.

Триггерный регистр 2, запись информации в который осуществляется вторым синхросигналом t₂, необходим для того, чтобы сделать все состояния автомата устойчивыми и исключить влияние состязаний. Триггеры регистра 1 называются вспомогательными, а триггеры регистра 2 основными. Сигнал z₅ является сигналом «Ошибка», а сигнал z₆ сигналом принадлежности входной цепочки символов языку с грамматикой G”. Сигналы Р₁,Р₂,Р₃ закодированные сигналы входных символов, Р₄ сигнал признака конца цепочки. Сигналом НУ (начальная установка) триггеры автомата устанавливаются в начальное состояние.

В общем случае сложность реализации автомата, точнее дешифратора и комбинационной схемы, зависит от способа кодирования входных символов. Предположим, что входные сигналы закодированы двоичным кодом, тогда входные символы x₀?x₇ могут быть представлены тремя кодирующими переменными p₁,p₂,p₃. В качестве символа окончания входной цепочки может быть использован любой свободный входной символ из x₀?x₇. Если таких нет, то необходимо ввести дополнительный, обозначив его через переменную p₄.

Выделив в структурной схеме автомата дешифратор, можно упростить комбинационную схему и тем самым облегчить синтез автомата. С помощью дешифратора входные символы, закодированные двоичными переменными p₁,p₂,p₃, преобразуются в унитарный код, в котором только одна из переменных принимает значение 1, в то время как все другие равны нулю. Поэтому выходы дешифратора можно обозначить x₀?x₇. В свою очередь символ окончания входной цепочки р₄ принимает значение 1 по окончании любой входной цепочки.

Пусть входные символы закодированы так, что их номера являются десятичными эквивалентами двоичных кодов (N=p₁2⁰+ p₂2¹+p₃2²), тогда, составив таблицу кодов (табл.8), получим, например: x=p₁p₂p₃,…, x₇=p₁p₂p₃.

Таблица 8

Символ	р3	р2	р1
х0	0	0	0
х1	0	0	1
х2	0	1	0
х3	0	1	1
х4	1	0	0
х5	1	0	1
х6	1	1	0
х7	1	1	1

Реализация дешифратора, как и всех остальных частей автомата, должна быть выполнена на логических элементах одной серии интегральных микросхем. Выберем для реализации схемы автомата микросхемы серии КР555. Реализация дешифратора на микросхеме данной серии приводится на рис.14. Четыре инвертора на входе используются для снижения нагрузок на источники сигналов p₁,p₂,p_3,p₄. Логическую функцию ЗИ - НЕ выполняют 8 логических элементов. 8 инверторов на выходе позволяют получить сигналы унитарного кода x₀?x₇, инверсии этих сигналов (x₀?x₇) получаются непосредственно с входов элементов ЗИ - НЕ. Для реализации дешифратора в указанном виде необходимо 16 инверторов и 8 логических элементов ЗИ - НЕ. В принципиальной схеме инверторы реализуются на микросхеме КР555ЛН1, содержащей в одном корпусе 6 инверторов, логические элементы ЗИ - НЕ на микросхеме КР555ЛА4. Так как для работы комбинационной схемы при фиксации конца цепочки могут быть необходимы сигналы p₄ ир₄, то для их формирования используются два инвертора 15, 16.

Комбинационная схема автомата реализует функцию его переходов, заданных графом переходов или таблицей переходов, с учетом выбранного варианта кодирования состояний. Все дальнейшие построения проводятся для варианта размещения, представленного на рис.12.



Рис.14

Построить функцию переходов это значит найти переключательную функцию кодирующих (внутренних) z₁?z₄ переменных. В соответствии со структурной схемой автомата каждая внутренняя переменная представляет состояние элемента памяти - триггера. По переключательным функциям внутренних переменных могут быть найдены функции возбуждения соответствующих им триггеров. Реализация этих функций образует комбинационную схему автомата. Сложность функции возбуждения, а значит и сложность комбинационной схемы, в общем случае зависит от типа триггера. Известны основные три типа триггера, используемые в элементах памяти - D-триггер, RS-триггер и Т-триггер. В принципе, можно использовать любой из типов триггеров, однако мы остановим свой выбор на триггере типа D. D-триггер лишь задерживает входной сигнал, поэтому его функция возбуждения D совпадает с функцией переключения внутренней переменной z_i. Запишем функции возбуждения D-триггеров для рассматриваемого примера и результаты занесем в табл.9.