TVPS_posobie_13_06_2013

3.4.Основная модель конечного автомата

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

Ранее мы рассматривали КА, который в каждый момент времени принимает один входной сигнал (символ входного алфавита) и выдает один выходной сигнал (символ выходного алфавита). Соответственно КА имеет один вход и один выход. Для решения практических задач часто может потребоваться устройство, которое имеет n входов и m выходов.

Чтобы моделировать с помощью КА устройства с n входами и m выходами, будем считать, что на вход автомата подается сигнал в виде вектора длины n. Соответственно на выходе автомата сигнал в виде вектора длины m. Тогда входной и выходной алфавиты представляют все возможные векторы длины n и m соответственно,

компоненты которых принадлежат некоторым	множествам.
~	n	~	m	.
Обозначим эти множества A и B. А новые алфавиты A	A	, B

Введем следующие обозначения:

xi(t) – значение i-той компоненты входного вектора в момент времени t, это значение будет совпадать с одним из символов алфавита А;

yj(t) – значение j-той компоненты выходного вектора в момент времени t, это значение будет совпадать с одним из символов алфавита B;

q(t) – внутреннее состояние КА в момент времени t.

Тогда работа КА Мили может быть описана следующими уравнениями:

q(t+1)= (q(t), (x1(t), x2(t), …, xn(t))),

yj(t)=

j(q(t), (x1(t), x2(t), …, xn(t))),

(10)

j

, m , i

, n .

~

Если в x1, x2, …, xn

подаются в некоторый момент времени

(1)

a

(2)

a

(n)

где

a

(i)

A, то это интерпретируется

как

a =(a

,

,…,

),

подача

~

~

на один вход. y1, y2, …, ym снимается в виде символов

a

~

~

~

на

b =(b(1), b(2),…, b(m)), то это интерпретируется как получение b

151

одном выходе. Тогда независимо от того, сколько входов и выходов первоначально имел КА, он преобразуется в автомат с одним входом и одним выходом. В связи с этим в дальнейшем можно рассматривать автоматы с одним входом и одним выходом (11):

q(t+1)= ( q(t), x(t)),

(11)

y(t)= (q(t), x(t)).

3.5.Этапы решения задачи синтеза КА

Этап 1. Предварительный. На данном этапе формируются условия работы КА, определяются входы и выходы, общий закон появления выходных символов в зависимости от воздействия на входы. Определяются условия взаимодействия с другими автоматами и объектами. Если автомат сложный, то он разбивается на блоки, этот этап называется еще этапом блочного синтеза.

Этап 2. Получение абстрактного КА. Определяется поведение КА и устанавливаются правила его функционирования. Результат – КА, заданный матрицами, таблицей или графически.

Этап 3. Минимизация числа внутренних состояний КА.

Получение абстрактного КА приведенного вида. Результат выполнения этого этапа – минимальный КА (то есть автомат с минимальным числом внутренних состояний). На первой стадии происходит разбиение множества внутренних состояний на классы эквивалентности путем склеивания эквивалентных состояний. На втором этапе получают минимальный КА.

Этап 4. Кодирование внутренних состояний. Кодируются состояния входа, выхода, внутреннего состояния. Результат – канонические уравнения КА.

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

Этап 6. Электрический и другой расчет элементов построенной схемы.

152

Этап 7. Размещение деталей на платах, составление монтажных схем, технической документации.

Разделение на этапы является условным, некоторые этапы могут объединяться, некоторые отсутствовать.

3.6.Представление КА в форме системы

канонических уравнений

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

Пример 55. Для заданного в виде таблицы КА построить канонические уравнения (табл. 16).

Таблица 16

КА для примера 55

a/q	q1	q2	q3	q4	q5
0	q1, 0	q3, 0	q1, 0	q4, 1	q4, 0
1	q3, 1	q4, 0	q5, 0	q3, 0	q3, 1

Шаг 1. Закодируем внутренние состояния автомата. Поскольку у автомата пять состояний, потребуется трехсимвольный код (табл. 17). Входной и выходной алфавиты содержат только два символа, поэтому их кодировать не придется.

Таблица 17

Кодирование внутренних состояний автомата

	q1'(t)	q2'(t)	q3'(t)
q1	0	0	1
q2	0	1	0
q3	0	1	1
q4	1	0	0
q5	1	0	1

153

Шаг 2. Назначим начальное состояние, пусть это будет

состояние q1. Тогда в нулевой момент времени t=0 q1'(0)=0, q2'(0)=0, q3'(0)=1.

Шаг 3. Составим таблицу истинности (табл. 18).

Таблица 18

Таблица истинности для примера 55

x(t)	q1'(t)	q2'(t)	q3'(t)
0	0	0	0
0	0	0	1
0	0	1	0
0	0	1	1
0	1	0	0
0	1	0	1
0	1	1	0
0	1	1	1
1	0	0	0
1	0	0	1
1	0	1	0
1	0	1	1
1	1	0	0
1	1	0	1
1	1	1	0
1	1	1	1

y(t)	q1'(t+1)	q2'(t+1)	q3'(t+1)		Примечания
				Доопределяем
				произвольно
				Так как из табл. 17
0	0	0	1	видно, что q1, 0 q1,
				0
0	0	1	1	q2	q3
0	0	0	1	q3	q1
1	1	0	0	q4	q4
0	1	0	0	q5	q4
				Доопределяем
				произвольно
				Доопределяем
				произвольно
				Доопределяем
				произвольно
1	0	1	1	q1	q3
0	1	0	0	q2	q4
0	1	0	1	q3	q5
0	0	1	1	q4	q3
1	0	1	1	q5	q3
				Доопределяем
				произвольно
				Доопределяем
				произвольно

Теперь можно записать систему канонических уравнений.

Для y(t) удобнее использовать СДНФ, так как в столбце выходных значений единиц меньше (всего три), чем нулей.

Для q1(t) и q2(t) также удобнее использовать СДНФ, так как единиц в столбце всего четыре.

Для q3(t) удобнее использовать СКНФ, так как нулей в столбце всего три.

154

y(t)=

q1'(t+1)=

q2'(t+1)=

q3'(t+1)=

155

3.7.Основные задачи теории КА

Основные задачи теории КА – это задачи анализа поведения автомата, задачи диагностики и управления.

КА как преобразователь. Пусть задан инициальный автомат Vq диаграммой Мура, таблицей или матрицей. Требуется описать в указанных терминах осуществляемое автоматом Vq преобразование входной информации в выходную:

f: А* В*.

Таким образом, при решении этой задачи выполняется анализ отношений между входной и выходной информацией, а также входной информацией и состоянием.

Пример 56. Построить КА, удаляющий «лишние» пробелы (таковыми считаются пробелы, находящиеся в начале строки и пробелы, следующие за пробелом). Другими словами, для входной строки «_a_ _a» результат работы КА представим в виде: «a_a» (символ «_» используется для обозначения пробела).

Поскольку нам надо удалить всякий пробел, следующий за другим пробелом, то множество состояний автомата будет содержать всего два состояния – q1, «после пробела» и q2, «не после пробела». Входной алфавит A={0, 1}, где 0 обозначает пробел, 1 – символ, не являющийся пробелом, выходной алфавит B={0, 1, 2}, где 0 означает печать пробела, 1 – отсутствие действия (ничего не печатаем), 2 – печать символа, не являющегося пробелом. Тогда функции переходов и выходов определятся (табл. 19).

Таблица 19

КА, удаляющий «лишние» пробелы

a q q1 q2

0q1, 1 q1, 0

1q2, 2 q2, 2

Чтобы конструируемый автомат удалял лидирующие пробелы начальным должно быть состояние «после пробела» q1.

156

Пример 57. Конечный автомат Vq1 задан диаграммой (Рис. 95), начальное состояние отмечено звездочкой. Требуется определить реализуемое этим автоматом отображение f входных слов в выходные слова.

Рис. 95. КА для примера 57

Из диаграммы видно, что единственной стрелкой, при переходе по которой выходной символ отличен от входного, является стрелка с отметкой (0,1), ведущая от состояния q2 к состоянию q3. Так как переход в состояние q2 эквивалентен появлению на входе автомата в предыдущий момент единицы, то определяемое автоматом преобразование входного слова заключается в замене на единицу каждого нуля слова , расположенного после единицы.

Пример 58. Построить конечный автомат, удовлетворяющий условиям (q0, 010) = 100, (q0, 1011) = 0100, (q0, 00) = 11,

(q0, 0110) = 1001, где q0 – начальное состояние автомата.

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

157

Рис. 96. Диаграмма Мура для примера 58

Заметим, что граф, представленный на Рис. 96 не обладает условием полноты, поэтому все недостающие дуги доопределяют произвольным образом.

КА как распознаватель (акцептор). КА распознает входные слова и отвечает на вопрос: принадлежит ли поданное на вход слово заданному множеству. Для описания множества входных слов, распознаваемых автоматом, могут быть использованы регулярные выражения.

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

Рассмотрим слова 00, 1, 110, получающиеся из указанных подслов отбрасыванием последней буквы. Для каждого из начал этих слов , 0, 00, 1, 11, 110 выделим состояние автомата, в котором он будет оказываться, как только конец входного слова совпадет с соответствующим началом (выбирается самое длинное из таких начал, если их несколько). Обозначим эти состояния, соответственно q1, q2, q3, q4, q5, q6 (табл. 20).

158

Таблица 20

Построение КА как распознавателя

a\q		0	00	1	11			110
	q1	q2	q3	q4		q5		q6
0	q2, 0	q3, 0	q3, 0	q2, 0		q6, 0		q3, 0
1	q4, 0	q4, 0	q4, 1	q5, 1		q5, 11		q4, 1

КА как перечислитель. Пусть задан инициальный КА – Vq, который перечисляет множество входных слов. Такие автоматы используются в теории передачи информации, где множество слов на входе КА является важной характеристикой. Множество слов, перечисляемых КА, также может быть записано в терминах регулярных выражений.

Пример 60. Пусть имеется автомат V, который задан диаграммой Мура, начальное состояние автомата V не фиксировано

(Рис. 97).

Рис. 97. Диаграмма Мура для примера 60

Для определения множества тех слов, которые могут быть получены на выходе автомата V (при различных начальных состояниях) построим диаграмму (Рис. 98), полученную из исходной диаграммы заменой отметки (ai, bi) каждой стрелки на символ bi. Те слова, которые возникают при прохождении различных путей на полученной диаграмме как последовательности отметок стрелок этих путей, и представляют собой элементы искомого множества. Из диаграммы нетрудно установить, что такими словами являются произвольные слова в алфавите {0, 1}, не содержащие подслов 101 и

1001.

1 (111 11)

159

Рис. 98. Диаграмма Мура для примера 60

Задачи диагностики. В этих задачах рассматриваются процессы взаимодействия с конечным автоматом (так называемые эксперименты с конечным автоматом), целью которых является получение информации о тех или иных неизвестных до начала эксперимента характеристиках автомата. Типичной здесь является ситуация, когда для исследуемого автомата V известен некоторый класс априори возможных неисправностей, при возникновении которых автомат V превращается в один из автоматов V1, ..., Vn. Задача диагностики заключается тогда в отыскании простейшего в некотором смысле эксперимента, позволяющего идентифицировать рассматриваемый автомат с одним из автоматов V, V1, ... ,Vn.

Пример 61. Задан автомат Vq. Возможные неисправности этого автомата заключаются в изменении его начального состояния.

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

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

Таблица 21

КА для примера 61

a q q1 q2

0q1, 0 q3, 0

1q2, 0 q1, 1

q3

q1, 1

q2, 0

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

Таблица 22

160