1.7.2. Переход от гса к автомату Мили
В случае автомата Мили отметки состояний ставятся:
отметка ставится на дуге, исходящей из начальной вершины, и на дуге, заходящей в конечную вершину;
отметки ставятся на дугах, исходящих из операторных вершин;
отметки ставятся на дугах, заходящих в ждущие вершины.
Заметим, что если дуги, исходящие из двух операторных вершин, заходят в одну вершину, отметка ставится после объединения этих дуг. Если же в одну вершину (не конечную!) заходят дуги, исходящие из операторной и условной вершины, отметка ставится до объединения этих дуг. Если за операторной вершиной следует ждущая, отметка ставится после объединения дуг, исходящих из вершин.
Так как одна и та же вершина может следовать за несколькими операторными вершинами (иллюстрация справа), в общем случае число состояний в автомате Мили меньше, чем число состояний в эквивалентном ему автомате Мура.
Пример. Для предыдущей ГСА отметки состояний расставляются следующим образом. Число состояний здесь на два меньше, чем в эквивалентном автомате Мили.
Функция переходов автомата Мили находится
так же, как и для автомата Мура. Функция
выходов находится следующим образом:
если простой путь, соединяющий состояния
и
,
заканчивается операторной вершиной,
то функция выхода, соответствующая
этому пути, есть множество записанных
в операторной вершине микроопераций,
иначе функция выхода есть
.
Пример. Диаграмма переходов-выходов автомата Мили, построенного по последней ГСА, выглядит следующим образом.
1.8. Задачи
Задача 1. Опишите систему, которая может быть представлена конечным автоматом. Задайте входной, выходной и внутренний алфавиты и функции переходов и выходов. Обоснуйте выбор множества состояний.
Задача 2. Построить конечные автоматы.
Автомат выдает единицу, если суммарная длина серий, содержащих не менее двух единиц, нечетная, и ноль в противном случае. Пример:
вход
1
0
1
1
1
0
1
0
0
1
1
0
1
1
1
0
выход
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
0
Автомат выдает единицу, если число серий, содержащих не менее двух единиц, нечетно, и ноль в противном случае. Пример:
вход
1
0
1
1
1
0
1
0
0
1
1
0
1
1
1
0
выход
0
0
0
0
0
1
1
1
1
1
1
0
0
0
0
1
Автомат выдает единицу, если число серий, содержащих нечетное число единиц, нечетно, и ноль в противном случае. Пример:
вход
1
0
1
1
1
0
1
0
0
1
1
0
1
1
1
0
выход
0
1
1
1
1
0
0
1
1
1
1
1
1
1
1
0
Автомат выдает единицу, если число серий, содержащих ровно две единицы, нечетно, и ноль в противном случае. Пример:
вход |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
выход |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
Задача 3. Грузовой лифт, обслуживающий трехэтажный магазин, имеет кнопку вызова на каждом этаже. Если нажата одна кнопка, то лифт движется на этаж, где расположена данная кнопка; если нажаты две или три кнопки, то лифт движется на самый нижний из всех этажей, на которых нажаты кнопки. Ни одна кнопка не может быть нажата во время движения лифта. Описать автомат, управляющий работой лифта (вход – нажатые кнопки, выход – направление, в котором движется лифт, и число этажей, которые он пройдет без остановки).
Задача 4. На рисунке изображена схема
,
на которую поступают сигналы от двух
импульсных генераторов напряжения
и
.
Каждый генератор генерирует положительный
или отрицательный импульс с периодом
1 микросекунда. Элемент
задерживает импульс на 1 микросекунду.
Схема
выдает положительный импульс, когда
оба поступающих на ее входы импульса
положительны, и отрицательный во всех
остальных случаях. Описать закон
функционирования схемы конечным
автоматом.
Задача 5. На рисунке представлена
модель нервной сети, где нервное волокно
соединено с источником, который генерирует
стимулы 0 или 1 в моменты времени
.
Большой кружок представляет нейрон.
Выход нейрона в момент
возбужден (т.е. принимает значение 1)
только в том случае, когда разность
между числом его возбужденных «возбуждающих
входов» (маленькие белые кружки) и числом
его возбужденных «тормозящих входов»
(маленькие черные кружки) в момент
равна или превышает его «порог» (число,
записанное внутри большого кружка).
Описать с помощью конечного автомата
закон функционирования сети.
Задача 6. Работа вычислительного устройства, имеющего вход и выход , определяется булевыми уравнениями
Записать эквивалентную диаграмму переходов-выходов автомата.
Задача 7. На вход устройства поступают нули и единицы. Построить конечный автомат, осуществляющий суммирование единиц по модулю .
Задача 8. Синтезировать конечный автомат, осуществляющий поразрядное сложение двух чисел в двоичной системе счисления.
Задача 9. Показать, что с помощью конечного автомата нельзя реализовать умножение двоичных чисел.
Задача 10. Построить конечный автомат, регулирующий пешеходный переход по запросу пешеходов.
Задача 11. На дороге с односторонним
движением установлены два датчика,
расстояние между которыми равно
.
Длина легковой машины меньше
,
длина грузовой машины больше
.
С датчиков поступает сигнал на сигнальное
устройство, проезжает ли мимо датчика
машина. Сигнальное устройство должно
сообщать, какая именно машина проезжает
по дороге. Синтезировать автомат,
описывающий работу сигнального
устройства.
Задача 12. Рядом с конвейером установлены два датчика-фотоэлемента, передающие сигнал на устройство сброса. Расстояние между датчиками равно . Детали на конвейере могут быть различной длины (как больше, так и меньше ). Деталь сбрасывается, если расстояние между ней и предыдущей деталью меньше . Синтезировать автомат, управляющий устройством сброса.
Задача 13. По заданной СФП построить ГСА, а затем графы автоматов Мили и Мура.
Задача 15. По заданной ГСА построить диаграммы переходов-выходов автоматов Мили и Мура. Записать СФП, эквивалентную заданной ГСА.
