дзержинский и воронцов 2

3

Определение и способы задания конечного автомата

Описательные определения: Конечный автомат – это устройство M имеющее входной и выходной канал и находящееся в каждой из дискретных моментов времени, называемых тактовыми моментами, в одном из конечных состояний. По входному каналу в каждый момент времени t = 1, 2… в устройство M поступают входные сигналы из некоторого конечного множества сигналов, указывается закон изменения состояния к следующему моменту времени в зависимости от входного сигнала и состояния, в котором находится устройство. Выходной сигнал в каждый момент времени зависит от состояния устройства и входного сигнала в текущий момент времени.

Определение: Конечным автоматом называется система M = { A, Q, B,G , F }, где A = {a1,…,an} – входной алфавит. Q = {q1,…,qn} – множество состояний автомата. B = {b1,…,bn} – выходной алфавит. Функция F(a, q): (A×Q → B) называется функцией выходов. Если a A, q Q то F(a, q) B. Функция G(a, q) называется функцией переходов: G : A×Q → Q. Если a A, q Q то G(a, q) Q.

Если в момент времени t = 1, 2… на вход автомата последовательно подаются входные символы x(t) A и автомат находится в состоянии q(t-1) Q, то под воздействием символа x(t) автомат перейдёт в новое состояние q(t) и выдаст выходной символ z(t). Величины x(t), q(t-1), q(t), z(t) связанны между собой следующими уравнениями, называемыми канонические уравнения автомата.

q(t) = G(x(t), q(t-1))

z(t) = F(x(t), q(t-1))

Автоматная таблица. Из определения конечного автомата следует, что его всегда можно задать таблицей, содержащей, m – строк и n – столбцов

Таблица 1

4

Каждая строка таблицы однозначно соответствует некоторому входящему сигналу, а столбец – некоторому состоянию автомата M. В клетку таблицы, стоящей на пересечении строки, соответствующей входящему символу ai и столбца, соответствующего состоянию qj, записывается пара G(ai, qj); F(ai, qj).

Диаграмма Мура. На плоскости рисуем n кругов, каждый взаимнооднозначно соответствуют состояниям q1,…,qn автомата M. Внутри каждого круга записываются соответствующие состояния. Из каждого круга проводится m – стрелок, взаимнооднозначно соответствующих символам входного алфавита A = {a1,…,an}. стрелке, соответствующей букве aj A и входящей из круга qj Q, приписывается пара (ai; F(ai, qj)) эта стрелка ведёт в круг соответствующей состояния q’, если q’ = G(ai, qj).

Примеры: Элемент задержки

Опр. Автомат с выходным состоянием q0, именуемый начальным, называется инициальным автоматом. Инициальный автомат представляет собой систему Mq0 = {A, Q, B, G, F, q0}. Если инициальный автомат задан таблицей или диаграммой Мура, то начальное состояние q0 отмечается некоторым символом, например *. При задании инициального автомата каноническими уравнениями к уравнениям добавляется соответствующее начальное условие q(0) = q0. Из определения инициального автомата следует, что любой автомат M с n – состояниями задаёт n – инициальных автоматов. В то же время знание всех этих инициальных автоматов полностью определяет автомат M.

Опр. Конечный автомат называется логическим, если все его алфавиты представляют собой булевы кубы соответствующих размерностей. A=Be, Q=Br, B=Bs. Тогда функция переходов G является системой булевых функций осуществляющих отображение булева куба Be+r в булев куб Br. А функция F является системой булевых функций осуществляющих отображение булева куба Be+r в булев куб Bs.

Задание конечного автомата системой булевых функций.

Пусть M = {A, Q, B, G, F} – конечный автомат, заданный таблицей или диаграммой Мура. Если автомат не является логическим, то его тоже можно задать системой булевых функций. Но для этого надо провести двоичное кодирование алфавитов.

Алгоритм задания автомата системой булевых функций.

1.Находим числа e, r, s, удовлетворяющие условиям

5

2e-1<m = |A| ≤ 2e;

2r-1<n = |Q| ≤ 2r;

2s-1<k = |B| ≤ 2s.

Очевидно, что e, r, s равны соответственно числу разрядов в двойном представлении чисел m, n, k.

2. Кодирование состояний, входных и выходных символов исходного автомата проводим следующим образом: каждому a A взаимнооднозначно ставим в соответствие булев вектор размерности e: x(a)=x1…xe. Аналогично каждому q Q и каждому b B ставим взаимнооднозначно в соответствие булев вектор α(q)= α1…αr и z(b)=z1…zs.

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

Эта таблица содержит 2e+r строк и e + 2r + s столбцов. В первых e+r столбцах выписаны все булевы вектора длинны e+r в порядке возрастания их номеров. Каждый такой вектор соответствует паре (x, α), где x – код входного символа, α – возможный код некоторого состояния.

4.Заполнение последних r+s столбцов таблицы:

Для каждой пары (a, q) a A, q Q, находим код x(a) и α (q). По таблице автомата определяем G(a, q) = q’ и F(a, q) = b. Затем находим код α(q’) = α’1, α’2…α’r и код z(b) = z1…zs. В строку таблицы соответствующую набору x1, x2…xe, α1…αr записываем набор α’1, α’2…α’r z1, z2…zs.

6

5. В результате выполнения пункта 4 может оказаться, что не все строки в таблице будут заполнены. Это произойдёт в том случае, если хотя бы одно из чисел n, k не является степенью 2 таким образом функции g1…gr, f1…fs окажутся не полностью определёнными, т.е. на некоторых наборах их значения не определены. Тогда мы их доопределяем произвольным образом так, чтобы получаемые полностью определённые функции удовлетворяли тем или иным условиям оптимальности, например, представлялись минимальными ДНФ.

Замечание: Один и тот же автомат может быть задан разными системами булевых функций. Это следует, во-первых, из того, что кодирование состояний и входных символов можно производить различными способами, и, во-вторых, доопределение функцией g1,…,gr, f1,…,fs также производится неоднозначно.

Каноническая система булевых функций будет иметь вид

(*)

g1(t) = g1(x1(t),…,xe(t), q1(t-1),…,qr(t-1))

…

gr(t) = gr(x1(t),…,xe(t), q1(t-1),…,qr(t-1)) z1(t) = g1(x1(t),…,fe(t), q1(t-1),…,qr(t-1))

…

zr(t) = zr(x1(t),…,fe(t), q1(t-1),…,qr(t-1))

Реализация конечных автоматов схемами.

Если автомат задан канонической системой булевых функций, то его можно реализовать в виде схемы из функциональных элементов и элементов задержки. Система функций реализуемых функциональными элементами предполагается полной. Эти схемы называются логическими сетями (ЛС) или синхронными логическими сетями (СЛС) или комбинационными схемами. Они строятся по тем же правилам, что и схемы из функциональных элементов, но добавляется правило введения обратной связи которое состоит в том, что в каждом контуре содержится хотя бы один элемент задержки.

Опр. Состояние комбинационной схемы в момент времени t – это совокупность состояний эл. задержек.

Утверждение: Произвольный конечный автомат может быть реализован в виде СЛС, причем количество элементов задержки равно наименьшему целому числу, которое превосходит log2|Q|

7

Чтобы построить комбинационную схему из элементов данного базиса с задержками описываемую системой канонических уравнений (*), обозначим qi(t) через qi , qi(t-1) через qi * , xj(t) через xj zk(t) через zk

Получим систему

(**)

qi = qi(x1,…,xe, q’1,…,q’r)

zk = fk(x1,…,xe, q’1,…,q’r) i = 1,…r

k = 1,…s

Функции в правых частях системы (**) надо представить формулами над данным базисом. Строим функциональную схему из элементов данного базиса реализующую функции qi и zk (i = 1…r; k = 1…s) и имеющую входами переменные x1,…,xe , q’1,…,q’2.

Затем каждому выходу qj через свой элемент задержки (зi) подаём на соответствующий вход q’j. Получим искомую комбинационную схему с задержками (или синхронную логическую схему) реализующую исходный автомат.

Автоматы Мура.

Пусть M = {A, Q, B, G, F} – автомат Мура, т.е. у него функции выхода в канонической схеме зависят только от состояний z(t)=F(q(t-1)) и не зависит от входящего символа в данный момент времени. В случае авт. Мура в диаграмме Мура все стрелки, выходящие из состояния q помечена буквой a, той же выходной буквой, поэтому принято для этих автоматов выходную букву писать над состоянием, а не над стрелкой. Выходные буквы наз. Метками состояний. В автоматной таблице также удобнее выходные буквы располагать в отдельной строке, так как в каждом столбце, не зависимо от входного символа, выходной символ один и тот же.

Простейшим автоматом Мура является задержка. Все то, что делает автомат Мили, может делать и автомат Мура.

Утверждение: (теорема) Для любого автомата Мили существует, покрывающий его автомат Мура. (Т.е. существует автомат Мура, который может производить все автоматные отображения, которые производит исходный автомат.

Доказательство: Допустим у исходного автомата мн. Q={q1,…,qn}

8

A={a1,…,an}. Надо построить автомат Мура, который делает все тоже самое, что и исходный. Построим автомат Мура. M’ = { A, Q’, B, C’, F’}, у которого

Q’ = {q10…qr0, q11…qr1, …, q1n...qnr} |Q’| = r + rn

Функции определим следующим образом

F’’(qi0) = -

F’(qij) = F(aj, qi)

G’(ak, qi0) = qik

G’(ak, qij) = qlk,

где l определяется из следующего условия:

ql = G(aj, qi)

Если исходный автомат находится в состоянии qi и на вход подается символ aj, то исходный автомат переходит в состояние ql = G(aj, qi). Построенный автомат Мура М’ покрывает исходный автомат М. Для всякого состояния qi автомата М, покрывающим для него состоянием является qi0 Q

Пусть α = ai1, ai2…ai9 A* любое входное слово F(qi, α) = ωk1, ωk2…ωk9 – выходное слово.

Рассмотрим соответствующее выходное слово автомата М’, если он находится в каждый момент времени в состоянии qi0 и покажем, что эти два слова совпадают, если прочерк не учитывать.

Рассмотрим работу этих автоматов.

Новый автомат выдает те же самые выходные символы, что и исходный, но с задержкой на один такт.

Основные соединения автоматов.

1. Тривиальные параллельные соединения автоматов — это совокупность 2х автоматов с независимыми входами и выходами.

Если

M1 = { A1, Q1, B1, C1, F1, G1 }

9

M2 = { A2, Q2, B2, C2, F2, G2 }

то у автомата М входной алфавит А = А1×А2, B = B1×B2, Q = Q1×Q2 Параллельное соединение автоматов, когда M1 = {A, Q1, B1, C1, F1,

G1} M2 = {A, Q2, B2, C2, F2, G2} у М : B = B1×B2, Q = Q1×Q2

2.Последовательные соединения.

A=A1; B=B2; Q=Q1×Q2

3.Соединения с обратной связью.

Имеется некоторый автомат М1 и автомат Мура М2. Некоторый вход у автомата М1 является выходом автомата Мура М2 и наоборот.

Замечание. Возможны модификации, при которых происходит более мелкое разбиение алфавитов.

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

Триггеры:

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

Полный автомат Мура с двумя состояниями называется триггером.

F(q) ≡ q

1.D-триггер (линия задержки) . RS -_триггер. JKтриггер.

D-триггер

Таблица 3

10

RS -_триггер

Таблица 4

Так как разные состояния полного автомата Мура дают различные выходы,

то можно считать, что между алфавитом состояний Q и выходным алфавитом B имеются взаимооднозначные соответствия. Поэтому можно считать, что алфавит Q и B совпадают . Отождествив соответствующие буквы алфавитов. Тогда F(q)=q, то есть функция выходов будет тождественной и в определении полного автомата Мура может не указываться.

Рассмотрим некоторую совокупность автоматов ∑.

Определение: Система ∑ называется автоматно-полной, если любой конечный автомат может быть реализован в виде ССА, в которой участвуют только автоматы из системы ∑ (ССА над cистемой ∑).

Теорема (достаточное условие автоматной полноты).

Для того чтобы система автоматов была полной, достаточно чтобы она

11

содержала хотя бы один полный автомат Мура и некоторую функциональнополную систему функциональных элементов. { M, f1…fS }

Доказательство. Было доказано, что любой автомат может быть представлен в виде СЛС, которая состоит из линии задержки и из некоторой функционально-полной системы функциональных элементов. Для доказательства теоремы достаточно доказать, что линии задержки можно представить в виде схемы над заданной системой .

Представим линии задержки в виде схемы автоматов следующего вида: есть входящий сигнал х(t), есть полный автомат Мура М, логические блоки F и Ф, то есть комбинационные схемы, содержащие функциональные элементы f1…fS F – блок выхода. Ф – блок возбуждения памяти. Они формируются следующим образом. Так как М – полный автомат Мура, то берем фиксированные два состояния q0 и q1 QM и будут существовать буквы а0 и а1, так что для q при подаче на вход М буквы а0 переведет автомат М в состояние q0, а при подаче на вход а1 переведет автомат М в состояние q1. Пусть блок Ф выдает букву а0, если на вход получил х=0, а автомат М находился в состоянии q, и выдает букву а1, если на вход подается х=1, а автомат М находится в состоянии q, то есть если на вход блока Ф послать сигнал 0, то блок Ф выработает сигнал, переводящий автомат М в состояние q0, а если на вход блока Ф послать сигнал 1, то блок Ф выработает сигнал, переводящий автомат М в состояние q1.

Блок F на состояние q0 создает символ 0, а на состояние q1 символ 1, а на остальных состояниях выход доопределяем произвольным образом. Такой автомат работает как задержка.

Если на вход х=0, то выход Ф равен a0(q), то есть q → q0, а на выходе F будет 0, но через один такт (так как стоит полный автомат Мура).

Если на вход х=1, то выход Ф равен? a1(q), то есть q → q1, а на выходе F будет 1, но через один такт.

Пример.

Структурный синтез автоматов

Пусть задана некоторая автоматно полная система Σ. Требуется представить автомат схемой (ССА) над Σ. Это называется структурный синтез.

Каноническая программа синтеза (алгоритм Хоффмана-Глушкова)

1)По описанию автоматического отображения составляется автоматная таблица.

2)Минимизируется число состояний полученного автомата.

3)Производится двоичное кодирование алфавита.

12