Синтез конечных автоматов. (до 90 минут)

Задача синтеза автомата состоит в построении автомата с наперед заданным поведением или функционированием. Реализация конечного автомата <A, Q, B, d,l > сводится к синтезу соответствующей комбинационной схемы, преобразующей входные переменные a_i(t)ÎА и q_j(t)ÎQ в выходные переменные b_k(t)ÎB и q_l(t+1)ÎB в соответствии с заданными характеристическими функциями d(t+1)=d(q_j(t), a_i(t)) и b_k(t)=l(q_j(t), a_i(t)). Для сохранения состояний q_l(t+1) до следующего такта в цепь обратной связи вводится необходимое количество элементов памяти.

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

Пример: Построим таблицу соответствия для конечного автомата, заданного графом.

Решение: Преобразуем автоматную таблицу для этого графа к виду:

ai	a0 a0 a0 a0	a1 a1 a1 a1	a2 a2 a2 a2	a3 a3 a3 a3
qj(t)	q0 q1 q2 q3	q0 q1 q2 q3	q0 q1 q2 q3	q0 q1 q2 q3
ql(t+1)	q3 q3 q3 q3	q2 q2 q2 q0	q1 q1 q2 q0	q3 q3 q3 q1
bk(t)	b0 b1 b1 b0	b0 b0 b0 b0	b0 b0 b1 b1	b0 b1 b1 b1

Сопоставляя

Получим таблицу соответствия:

Переменные	Логические функции
ai(t)	qj(t)	ql(t+1)	bk
x1	x2	y1	y2	z1	z2

Из этой таблицы видно, что три логические функции являются функциями четырех аргументов. Это означает, что комбинационная схема должна иметь четыре входа, соответствующие входным переменным x₁, x₂ и переменным состояния у₁, у₂, а также три выхода, соответствующие переменным состояния z₁, z₂ и выходной переменной b. Синтезировав комбинационную схему, соответствующую полученной таблице (т.е. записав для каждой из 3-х логических функций ее С.Д.Н.Ф. и минимизировав и минимизировав их в булевом базисе элементов "и", "или", "не" и представив эту схему) и введя два элемента задержки З₁ и З₂, получим структурную схему автомата:

Лекция №10.

ИЗОМОРФИЗМ И ЭКВИВАЛЕНТНОСТЬ КОНЕЧНЫХ АВТОМАТОВ.

Продолжительность: 2 часа (90) минут

Ключевые (основные) вопросы (моменты)

Текст лекции

Дата добавления: 2015-12-01