Лабораторная работа № 2 Синтез автомата по регулярным выражениям

Цель работы: изучение синтеза цифрового автомата, алгоритм которого представляется в виде регулярных выражений.

Теоретические сведения

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

Не существует сейчас и никогда не будет создан алгоритм перехода от словесной формы описания функционирования автомата к математически строгому описанию. Математика оперирует только с математическими понятиями, а словесное описание к ним не принадлежит. Задание автомата на каком-либо формальном языке – процесс творческий и не обязательно легкий. Поэтому при выполнении абстрактного синтеза вводят какую-либо промежуточную форму представления автомата, переход к которой от описательной формы достаточно прост, а сама она, в свою очередь, облегчает переход к структурному синтезу. Исходной формой задания автомата для выполнения структурного синтеза может быть, например, орграф или таблицы переходов состояний и выходов. Требованиям к промежуточной форме представления автомата удовлетворяет задание автомата граф-схемой алгоритма, логической схемой алгоритма, регулярными выражениями и некоторыми другими способами.

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

Алгебру событий и основные алгоритмы синтеза автомата по регулярным выражениям разработал американский ученый С.К. Клини. Русский перевод его работы “Представление событий в нервных сетях и конечных автоматах” опубликован в сборнике “Автоматы” (Москва, Издательство иностранной литературы) в 1956 г. Усовершенствованный алгоритм синтеза автомата предложил советский ученый В.М. Глушков [1].

Основные понятия, определения и законы алгебры событий [1, 3, 12]

Слово – конечная последовательность символов, принадлежащих некоторому множеству символов. Можно говорить о слове в рамках входного алфавита, в рамках выходного алфавита. Если, например, алфавит Y содержит три символа y₁, y₂, y₃, т.е. Y = {y₁,y₂,y₃}, то возможны слова y₁, y₁y₁y₁, y₂y₁, y₃y₃y₂y₁y₂, y₃, y₃y₁y₂y₁ и так далее.

Пустое слово – слово нулевой длины. Пустое слово принято обозначать буквой e. Для любого слова d выполняется соотношение ed = de = d. Считается, что пустое слово принадлежит любому алфавиту символов.

Событие – произвольное множество конечных слов, составленных из букв входного алфавита X = {x₁,x₂,…,x_k}. В дальнейшем событие будем обозначать буквой H.

Элементарное событие в алфавите X = {x₁,x₂,…,x_k} – это какое-либо из (k + 1)-го элементарных событий x₁, x₂,…, x_k, e, где e – пустое слово.

Пусть на вход автомата S, предварительно установленного в начальное состояние a₀  A = {a₀, a₁,…, a_n-1}, поступает слово, составленное из символов входного алфавита X = {x₁, x₂,…, x_k}, которое вызывает на выходе автомата появление символа y_i  Y = {y₁,…, y_p}. Входные слова, на которые автомат откликается выходным символом y_i, можно объединить в множество H_i(x₁, x₂,…, x_k). Это множество называется событием, представленным в автомате S выходным символом (буквой) y_i.

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

Полностью определенный автомат можно задать таблицей, устанавливающей соответствие между попарно непересекающимися событиями H_i(x₁, x₂,…,x_k) и выходными символами y₁,…,y_i,…,y_p (табл.4.1). Аналогичную таблицу для частичного (не полностью определенного) автомата необходимо дополнить событием H_запр запрещенных входных слов (табл.4.2).

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

Таблица 4.1 Таблица 4.2

Таблица событий полного автомата, Таблица событий частичного

представленных выходными автомата, представленных

буквами y₁, y₂, …, y_p выходными буквами y₁, y₂, …, y_p

	Буква			Буква
Событие	выходного		Событие	выходного
	алфавита			алфавита
H1(x1, x2, …, xk)	y1		H1(x1, x2, …, xk)	y1
H2(x1, x2, …, xk)	y2		H2(x1, x2, …, xk)	y2
				
Hp(x1, x2, …, xk)	yp		Hp(x1, x2, …, xk)	yp
			Hзапр(x1, x2, …, xk)	не определена

Любое событие, имеющее конечное множество слов, является регулярным. Если событие состоит из бесконечного множества слов, то оно может быть регулярным или нерегулярным.

Дизъюнкцией (от латинского disjunctio – разделение, различие) событий H₁, H₂, …, H_n называется событие H = H₁H₂H_n состоящее из всех слов, встречающихся в событиях H₁, H₂, …, H_n. Другое название дизъюнкции – логическое ИЛИ.

Конкатенацией (от английского concatenation – сочленение) двух слов M и N называется такое слово Z, которое получается в результате непосредственного слияния слова M, стоящего слева, и слова N, стоящего справа. Например, если M = x₁x₂x₅, N = x₄x₃x₄, то конкатенация M и N – это слово Z = x₁x₂x₅x₄x₃x₄. В общем случае операция конкатенации некоммутативна. Иногда операцию конкатенации по сходству с формой записи называют умножением, но это не вполне правильно.

Итерацией (от латинского iteratio – повторение) события H называется событие [H] , состоящее из пустого слова e и всех слов вида H, HH, HHH и так далее до бесконечности. Итерация пустого события равна пустому событию: [e] = e. Итерация события H определяется как [H] = [e]HHHHHH, где [ ]– итерационные скобки.

Примечание. В книгах [1] и [3] для обозначения итерации использованы фигурные скобки, а для списков элементов множеств – круглые скобки. В книге [12] итерация H записывается как H*.

Регулярное событие может быть задано регулярным выражением, т.е. формулой, содержащей символы e, символы входного алфавита и знаки регулярных операций над ними. Одно и то же регулярное событие может быть представлено разными эквивалентными регулярными выражениями. Ниже приведены некоторые из наиболее важных тождественных соотношений алгебры событий, которыми можно пользоваться при преобразованиях и упрощениях формул. Буквами H, H₁, H₂ и H₃ обозначены произвольные события.

• H₁H₂ = H₂H₁ – коммутативность дизъюнкции событий,

• H₁(H₂H₃) = (H₁H₂)H₃=H₁H₂H₃ – ассоциативность дизъюнкции событий,

• HH = H – идемпотентность дизъюнкции событий, (идемпотентность – от латинского idempotens – сохраняющий ту же степень, силу),

• H₁(H₂H₃) = (H₁H₂)H₃=H₁H₂H₃ – ассоциативность конкатенации событий,

• H₁(H₂H₃) = H₁H₂H₁H₃ левая и правая дистрибутивность событий

(H₁H₂)H₃ = H₁H₃H₂H₃ по отношению к дизъюнкции,

• [[H]] = [H] – идемпотентность итерации события,

• [H] = eH[H] – правило развертывания итерации события,

• H[H] = [H]H – закон коммутативности для итерации события,

• [H][H] = [H] – закон мультипликативного поглощения для итерации события,

• [H]H = [H] – закон дизъюнктивного поглощения для итерации события.

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

Таблицу состояний можно получить из регулярных выражений, а регулярные выражения можно вывести из таблицы состояний.