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