Сучкова Л.И. Абстрактный и структурный синтез автоматов
Подождите немного. Документ загружается.
141
3. Построить конечный автомат, добавляющий бит не-
четности к цепочке из 0 и 1.
4. При разбиении на информационные кадры при пере-
даче потока информации по каналам связи в сетях использу-
ется метод вставки начального и заключительного флагов
(обрамления кадра). Каждый кадр может содержать произ-
вольное число информационных битов, он начинается и
за-
канчивается специальной последовательностью 01111110,
называемой флагом. Границы между кадрами однозначно
распознаются приемным устройством, если в потоке битов
внутри кадра не встретится шесть единиц подряд. Для того
чтобы произвольный поток информации можно было переда-
вать таким методом, используется прием «вставка бита». По-
строить конечный автомат-кодировщик, подготавливающий
информационный кадр для передачи, вставляя
дополнитель-
ный нуль в информационный поток после каждых пяти под-
ряд идущих единиц (например, поток битов
0111111001011111110 автомат преобразует в
011111010010111110110)
5. Построить автомат, управляющий светофором авто-
матического регулирования транспорта на обычном перекре-
стке. Движение регулируется так, что в одном направлении
разрешено движение T
1
секунд, в другом – Т
2
секунд. Един-
ственным входным событием автомата является событие за-
вершения тайм-аута.
6. Построить конечный автомат, управляющий зачисле-
нием денег на счет сотового телефона. Считать, что номер
телефона состоит не более, чем из 3 символов, причем первая
цифра номера идентифицирует оператора сотовой связи. Ис-
пользуются купюры номиналом 10, 50, 100 рублей.
7. Построить модель
автомата, управляющего продажей
кофе различных видов. Имеет кнопки для выбора вида кофе,
для выполнения заказа, для сброса заказа и возврата денег.
Принимает монеты номиналом 1, 2, 5, 10 рублей.
8. Построить автомат, управляющий регулированием
транспорта на Т-образном перекрестке, на котором основной по-
ток тра
н
степенн
а
Ч
ет
ы
дый мо
ж
но, что
о
бы не с
о
сигнала
управле
н
— на п
е
ный, а н
а
Счи
т
движет
с
перекре
с
матичес
к
рах уст
а
появляе
т
ры <0,0
>
ходами
–
9.
П
секретн
ы
вующи
й
леров о
вида, п
р
более
о
нахожд
е
может з
н
спорта иде
т
а
я дорога (с
м
ы
ре светоф
о
ж
ет показы
в
о
ни должны
о
здавалась
а
«Зеленый»
н
ия выдает
е
рвом свето
ф
а
третьем —
т
ая, что тра
н
с
я редко, п
о
с
тком по за
п
к
и передаю
т
а
навливаетс
я
т
ся машина
>
; <0,1>; <
1
–
четверки с
П
остроить
м
ы
й архив
с
й
допуск, и
существля
е
р
ичем одн
о
о
дного сотр
е
ния в архи
айти в арх
и
1
4
т
с запада на
м
.рисунок).
о
ра управля
ю
в
ать один из
управлятьс
я
а
варийная с
и
на всех че
т
четверки с
и
ф
оре красны
й
желтый.
н
спорт в нап
р
о
строить ко
п
росам тран
с
т
ся с помощ
ь
я
значение 1
. Входами в
1
,0>: <1,1>
с
игналов све
т
м
одель авт
о
с
отруднико
в
контролер
о
е
тся по спе
ц
о
временно
в
удника, и,
ве сотрудн
и
и
в не более
ч
4
2
восток, а с
ю
т движен
и
трех сигна
л
я
согласова
н
и
туация (на
п
т
ырех свет
о
и
гналов, на
п
й
, на втором
р
авлении вт
о
нечный ав
т
с
порта. Запр
ь
ю сенсоров
α
, если в соо
т
автомат уп
р
с
остояний с
е
т
офоров.
о
мата, орга
н
в
фирмы, и
о
в. Вход со
т
ц
иальным
ж
в
архиве м
о
возможно,
и
ка не огра
н
ч
ем на врем
я
юга подход
и
и
ем транспо
р
л
ов: К, Ж, 3.
н
но, причем
п
ример, не
о
форах). Ус
т
п
ример, <К;
и четверто
м
о
ростепенн
о
т
омат, упра
в
осы трансп
о
α
и β. На эт
и
т
ветствующ
р
авления с
л
е
нсоров α
и
н
изующего
д
меющих с
о
т
рудников
и
ж
етонам ра
з
о
жет наход
и
контролер
а
н
ичено, а к
о
я
Т.
и
т второ-
р
та, каж-
Очевид-
так, что-
было бы
т
ройство
3; Ж; 3>
м
— зеле-
о
й дороги
в
ляющий
о
рта авто-
и
х сенсо-
ем месте
л
ужат па-
и
β, а вы-
д
опуск в
о
ответст-
и
контро-
з
личного
и
ться не
а
. Время
о
нтролер
143
10. Построить конечный автомат, управляющий работой
автоматической стиральной машины, которой для работы
требуется наличие моющего вещества (контролируется спе-
циальным датчиком), установка температуры нагрева. Име-
ются кнопки «Старт», «Стоп» и табло, на которое выводятся
сообщения о готовности, неисправностях и текущей опера-
ции.
11. Построить конечный автомат, управляющий работой
телефона с автоответчиком, который
в зависимости от номе-
ра абонента включает различные записи ответов. Считать,
что номер телефона состоит из 5 цифр, реагировать на по-
следние 2.
12. Построить конечный автомат, реализующий модель
телефонного коммутатора, который при наборе номера пред-
лагает набор дополнительных цифр (цифры) для соединения
с нужным абонентом. Если абоненту все равно с кем
разгова-
ривать, то он может нажать, например, цифру 0, тогда пода-
ется сигнал на все телефоны, подключенные к коммутатору.
Если дополнительная цифра не нажимается, то после истече-
ния некоторого времени связь с абонентом разрывается.
13. Построить конечный автомат, реализующий логику
работы домофона.
14. Построить конечный автомат, реализующий управле-
ние освещенностью в зависимости
от сигнала с фотоэлемента
и времени суток.
15. Построить конечный автомат, реализующий опреде-
ление факта проникновения в помещение при открытии две-
ри, на которой стоит датчик, реагирующий на электронный
ключ.
16. Построить конечный автомат, управляющий работой
микроволновки, работающей в различных режимах.
17. Построить конечный автомат, управляющий работой
кондиционера в зависимости
от температуры окружающей
среды и температуры вне помещения.
144
9 ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ ДЛЯ ИНТЕРПРЕТА-
ЦИИ РАБОТЫ АВТОМАТОВ И ИХ ПРЕОБРАЗОВАНИЙ
9.1 Общие сведения о функциях программы
Для облегчения выполнения заданий и проверки их пра-
вильности разработан программный комплекс. Структура
главного меню программы приведена на рисунке 9.1:
y Файл
− Создать
Конечный автомат-распознаватель
Конечный автомат Мили
Конечный
автомат Мура
Автомат с магазинной памятью
Машина Тьюринга
− Открыть
− Сохранить
− Сохранить как…
− Выход
y Справка
− О программе
− Помощь
Рисунок 9.1 – Главное меню программы
Пункт меню «Операции» становится доступным только
145
во время работы с автоматом того или иного вида. При этом
он содержит только такие подпункты, которые соответству-
ют операциям, применимым для данного вида автомата.
Структура пункта меню «Операции» для конечного ав-
томата-распознавателя (рисунок 9.2):
− Интерпретировать
Получить результат сразу
Получить результат по шагам
− Минимизировать
Получить результат
сразу
Получить результат по шагам
− Детерминировать
Получить результат сразу
Получить результат по шагам
Рисунок 9.2 – Меню «Операции» для конечного автомата-
распознавателя
Структура пункта меню «Операции» для конечного ав-
томата Мили (рисунок 9.3):
− Интерпретировать
Получить результат сразу
Получить результат по шагам
− Минимизировать
Получить результат
сразу
Получить результат по шагам
− Структурный синтез
− Перевод в автомат Мура
146
Рисунок 9.3 – Меню «Операции» для автомата Мили
Структура пункта меню «Операции» для конечного ав-
томата Мура (рисунок 9.4):
− Интерпретировать
Получить результат сразу
Получить результат по шагам
− Минимизировать
Получить результат сразу
Получить результат по шагам
− Перевод в Мили
Рисунок 9.4 – Меню «Операции» для автомата Мура
Структура
пункта меню «Операции» для автомата с
магазинной памятью и машины Тьюринга (рисунок 9.5):
− Интерпретировать
Получить результат сразу
Получить результат по шагам
Рису
н
Н
«Файл»
«Файл»
«Справ
к
Н
тами и
м
команд
ы
Поэтом
у
синтез
а
газинно
телем
п
остальн
на вкла
д
томато
в
зультат
а
н
ок 9.5 –
Ме
а панели и
н
– «
О
– «Открыт
ь
– «С
о
– «Сохран
и
– «
С
к
а» – «Пом
о
а панели и
н
м
еются кно
п
ы
меню «
О
у
не все кн
о
– к
н
а
втомата п
о
й памятью
п
равилам г
р
ых автома
т
д
ке «Кома
н
в
.
– кн
о
а
сразу». О
с
1
4
е
ню «Опера
ц
МП-ав
т
н
струменто
в
О
ткрыть»,
ь
»;
о
хранить»,
и
ть»;
С
правка»,
с
о
щь».
н
струменто
в
п
ки, больш
О
перации»
д
о
пки всегда
н
опка «Пос
т
о
заданному
команды с
т
р
амматики
н
т
ов – кома
н
н
ды». Кноп
к
о
пка «Инте
р
с
уществляе
т
4
7
ц
ии» для ма
т
омата
в
имеются с
л
соответств
у
соответств
с
оответств
у
в
формы д
л
инство из
к
д
ля заданн
являются в
и
т
роить авт
о
описанию.
т
роятся по
з
н
а вкладке
н
ды вводят
с
к
а доступн
а
р
претирова
т
т
интерпре
т
шины Тьюр
л
едующие
к
у
ет коман
д
ует коман
д
у
ет коман
д
л
я работы с
к
оторых ду
б
ого вида
а
и
димыми.
о
мат».Осу
щ
Для автом
а
з
аданным
п
«Граммати
к
с
я непосре
д
а
для всех
в
т
ь с получе
н
т
ацию авто
м
инга и
к
нопки:
д
е меню
д
е меню
д
е меню
автома-
б
лируют
а
втомата.
щ
ествляет
а
та с ма-
п
ользова-
к
а». Для
д
ственно
в
идов ав-
н
ием ре-
м
ата, при
этом вх
о
ленте.
К
О
выводо
м
ется о
д
должн
ы
видов а
в
зультат
а
Кнопка
распоз
н
ществл
я
точног
о
для кон
е
зультат
а
распоз
н
ется до
с
образов
структу
р
Мили.
та Мил
и
– преоб
р
о
дные данн
ы
К
нопка дост
у
– кно
п
О
существл
я
м
результа
т
д
на команд
а
ы
быть запи
с
в
томатов.
– кн
о
а
сразу».
О
доступн
а
н
авателя.
– кн
о
я
ет пошаго
в
о
результат
а
е
чного авто
– кн
о
а
сразу».
н
авателей, а
– кн
о
с
тупной дл
я
ателей Ми
л
– кн
о
р
ный синт
е
– кн
о
и
преобраз
о
р
азование
в
1
4
ы
е для авто
у
пна для вс
е
п
ка «Интер
п
я
ет интерп
р
т
ов работы.
а
. Входны
е
с
аны на ле
н
о
пка «Дете
р
О
существля
а
только
о
пка «Дете
р
в
ую детерм
и
а
на каждом
мата-распо
з
о
пка «Мин
и
Является
также прео
б
о
пка «Мин
и
я
автоматов
л
и и Мура.
о
пка «Стру
к
е
з абстракт
н
о
пка «Пере
в
о
вание в ав
т
в
автомат
М
4
8
мата долж
н
е
х видов ав
т
п
ретироват
ь
р
етацию ав
т
За каждый
е
данные
д
н
те. Кнопк
а
р
минироват
ь
ет детерм
и
для ко
н
р
минирова
т
и
низацию с
шаге. Кно
п
з
навателя.
и
мизироват
ь
доступно
й
б
разовател
е
и
мизироват
-распознав
а
к
турный си
н
н
ого автом
а
в
од». Осущ
е
т
омат Мура
,
М
или. Досту
п
н
ы быть зап
и
т
оматов.
ь
пошагово
»
т
омата с по
ш
шаг интер
п
д
ля автома
т
а
доступна
д
ь
с получе
н
и
низацию
а
н
ечного а
в
т
ь пошагов
о
выводом
п
п
ка доступ
н
ь
с получе
н
й
для ав
т
е
й Мили и
М
ь пошагов
о
а
телей, а та
к
н
тез». Осу
щ
а
та-преобр
а
е
ствляет дл
я
,
для автом
а
п
на только
и
саны на
»
.
ш
аговым
п
ретиру-
т
а также
д
ля всех
н
ием ре-
а
втомата.
в
томата-
о
». Осу-
п
ромежу-
н
а только
н
ием ре-
т
оматов-
М
ура.
о
». Явля-
к
же пре-
ествляет
а
зователя
я
автома-
а
та Мура
для этих
типов а
в
тов кн
о
Прерыв
9.
Д
л
следую
щ
л
в
т
п
п
т
к
претац
и
шагам).
К
р
вкладк
а
га(рису
н
Д
л
в
в
к
получе
н
получе
н
нок 9.7)
Д
л
в
в
в
п
в
томатов.
– кн
о
о
пка досту
п
ает интерп
р
2 Задание а
в
л
я автомат
о
щ
ие элемен
т
л
ента;
в
кладка дл
я
т
аблица дл
я
п
оля для в
ы
п
оле для в
ы
т
аблица дл
я
к
нопки па
н
и
я с получе
р
оме этого
д
а
для выво
д
н
ок 9.6):
л
я конечно
г
в
кладка дл
я
в
кладка дл
я
к
нопки па
н
н
ием сразу,
н
ием резуль
:
л
я конечно
г
в
ыходная л
е
в
кладка дл
я
в
кладка дл
я
п
оля для в
ы
1
4
о
пка «Отме
н
п
на во вре
м
р
етацию.
в
томатов р
а
о
в всех рас
с
т
ы:
я
ввода и ре
д
я
вывода си
н
ы
вода алфав
и
ы
бора начал
ь
я
выбора за
к
н
ели быстр
о
нием резул
д
ля машин
ы
д
а таблиц
ы
г
о автомата
-
я
вывода ма
т
я
вывода та
б
н
ели быстр
о
детермини
з
тата сразу,
г
о автомата
е
нта;
я
вывода ма
т
я
вывода та
б
ы
вода выхо
д
4
9
н
ить». Для
м
я пошаго
в
а
зличных т
и
с
матриваем
д
актирован
и
н
таксическ
и
и
та машин
ы
ь
ной коман
д
к
лючительн
ы
о
го запуска
ьтата сраз
у
ы
Тьюринга
ы
переходо
в
-
распознава
т
рицы пере
х
б
лицы пере
х
о
го запуск
а
з
ация по ш
а
минимизац
и
Мили и М
у
т
рицы выхо
б
лицы пере
х
д
ного алфав
и
всех видов
в
ой интерп
р
и
пов
ых типов
д
и
я команд;
и
х ошибок;
ы
Тьюринга
;
д
ы ;
ы
х состоян
и
(построит
ь
у
, интерпре
т
остается д
о
в
машины
Т
теля досту
п
х
одов авто
м
х
одов автом
а
(детемин
и
а
гам, мини
м
и
я по шага
м
у
ра доступн
ы
дов автома
т
х
одов;
и
та автома
т
автома-
р
етации.
д
оступны
;
и
й ;
ь
, интер-
т
ация по
о
ступной
Т
ьюрин-
п
ны:
м
ата;
ата;
и
зация с
м
изация с
м
) (рису-
ы
:
т
а;
а;
150
кнопки панели быстрого запуска (минимизация с по-
лучением результата сразу, минимизация по шагам, струк-
турный синтез) (рисунок 9.8).
Рисунок 9.6 – Пример формы для машины Тьюринга