Общие теоретические положения
Конечный автомат может быть задан словесным алгоритмом, таблицами переходов (ТП) и выходов (ТВ), графом состояний и системой уравнений, выражающих зависимости между входами, выходами и внутренними состояниями автомата. Последний (алгебраический) способ задания представляет собой математическую модель, по которой составляется схема, реализующая заданный алгоритм. Следовательно, в любом случае конечной формой задания автомата является алгебраическая, а порядок синтеза сводится к получению математической модели и функциональной схемы автомата и состоит из следующих этапов:
1) составление словесного алгоритма работы автомата;
2) определение числа состояний автомата;
3) составление таблиц переходов и выходов;
4) определение количества элементов памяти автомата;
5) кодирование таблиц переходов и выходов;
6) составление таблицы истинности конечного автомата;
7) получение математической модели автомата;
8) составление функциональной схемы;
9) составление принципиальной схемы.
Способы представления автоматов
Рассматриваем автоматы Мили и Мура – их еще называют автоматами I и II рода.
Автоматы можно представить : - таблицей, - графом.
Автомат Мили задается 2-мя таблицами: переходов и выходов, или одной – совмещенной таблицей переходов-выходов.
Автомат Мура задается одной таблицей, называемой отмеченной таблицей переходов.
|
|
|
Пример 1. Задан автомат А1 в табличном виде. Определить его входной и выходной алфавиты. Определить тип автомата и представить его в виде графа. Определить выходную последовательность букв, если на вход поступает входная последовательность вида Х1Х2Х3Х3Х1Х2.
| S0 | S1 | S2 | S3 | S0 | S1 | S2 | S3 | |||
| X 1 | S3 | S0 | S2 | S0 | X 1 | Y1 | Y2 | Y3 | Y5 | |
| X 2 | S1 | S2 | S0 | S3 | X 2 | Y1 | Y1 | Y4 | Y2 | |
| X 3 | S0 | S1 | S3 | S1 | X 3 | Y5 | Y4 | Y1 | Y5 |
Решение.
Входной алфавит: X={X1, X2, X3}. Выходной алфавит: Y={Y1, Y2, Y3, Y4, Y5}.
Таблицами задан автомат Мили.
Граф автомата:
При подаче на вход автомата входной последовательности вида Х1Х2Х3Х3Х1Х2 на выходе будет получена последовательность Y1Y2Y5Y4Y2Y1, на графе автомата соответствующие ребра выделены.
Пример 2. Задан автомат А2 в табличном виде. Определить его входной и выходной алфавиты. Определить тип автомата и представить его в виде графа.
| - | Y1 | Y3 | Y3 | Y2 | |
| q0 | q1 | q2 | q3 | q4 | |
| X 1 | q0 | q4 | q2 | q1 | q3 |
| X 2 | q4 | q3 | q0 | q2 | q4 |
| X 3 | q2 | q0 | q4 | q4 | q1 |
| X4 | q3 | q1 | q1 | q3 | q2 |
Решение.
Входной алфавит: X={X1, X2, X3, X4}. Выходной алфавит: Y={Y1, Y2, Y3}.
Таблицей задан автомат Мура.
Граф автомата:
|
|
|
Пример 3. Задан автомат А3 в виде графа. Определить его входной и выходной алфавиты. Определить тип автомата и представить его в табличном виде.
Решение.
Входной алфавит: X={X1, X2 }. Выходной алфавит: Y={Y1, Y2, Y3 }.
Графом задан автомат Мили.
Совмещенная таблица переходов-выходов:
| S0 | S1 | S2 | |
| X 1 | S2 Y2 | S0 Y1 | S1 Y1 |
| X 2 | S1 Y3 | S2 Y3 | S0 Y1 |
Пример 4. Задан автомат А4 в виде графа. Определить его входной и выходной алфавиты. Определить тип автомата и представить его в табличном виде.
Решение.
Входной алфавит: X={X1, X2 }. Выходной алфавит: Y={Y1, Y2, Y3 }.
Графом задан автомат Мура.
Отмеченная таблица переходов:
| - | Y1 | Y3 | Y2 | |
| q0 | q1 | q2 | q3 | |
| X 1 | q1 | q0 | q3 | q3 |
| X 2 | q2 | q3 | q1 | q0 |
Дата добавления: 2019-02-22; просмотров: 357; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!