Главная страница Случайная страница
Разделы сайта
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Способы задания конечного автомата
|
|
1°. Табличный способ задания. Поскольку для функций 
и 
области определения и значений принадлежат конечному множеству, то их задают при помощи таблиц.
Пример 1. Зададим автомат следующим образом: 
, 
, 
.Функцию определим с помощью таблицы переходов, а функцию 
– с помощью таблицы выходов.
Таблица 1. Таблица переходов Таблица 2. Таблица выходов
| Вход | Состояние | ||
| 
| 
| |
| 
|
|
|
|
| 
|
|
|
|
| 
|
| Вход | Состояние | ||
|
|
|
| |
|
| 
| 
| 
|
|
| 
| 
|
|
|
| 
|
| 
|
Если известна последовательность сигналов на входе автомата, то таблицами переходов и выходов однозначно определяется выходная последовательность.
2°. Графический способ задания. Используется диаграмма переходов-выходов. Она представляет собой ориентированный мультиграф, в котором каждому внутреннему состоянию автомата соответствует вершина. Переходы автомата из состояния в состояние изображаются стрелками, на каждой из которых пишутся входной символ, вызывающий данный переход, и выходной символ, вырабатываемый автоматом.
 
|
|
|
| 
| 
| 
| 
| 
| 
|
|
|
Рис.1 Диаграмма переходов-выходов
Пример 2. Требуется построить автомат, который работал бы следующим образом: в каждый такт на вход автомата поступают очередные двоичные разряды слагаемых, автомат вырабатывает соответствующий двоичный разряд их суммы. Для двухразрядных слагаемых имеем: 
, 
, 
.
Автомат находится в состоянии 1, если при сложении предыдущих разрядов возникает перенос, и в состоянии 0 – в противном случае. Диаграмма переходов-выходов показана на рис. 2.
| 1
|
| 0
|
10|1 00|1 11|1
Рис. 2
|
|