Навигация
Построение графа переходов абстрактного автомата
16157
знаков
12
таблиц
0
изображений
1.3 Построение графа переходов абстрактного автомата
Построим по таблице 2 граф переходов автомата. При этом предполагается, что последний символ каждого входного слова должен переводит автомат в начальное состояние.
Граф переходов абстрактного автомата представлен в приложении 1.
1.4 Минимизация абстрактного автомата
По графу переходов построим таблицу переходов-выходов заданного автомата (таблица 3).
Таблица 3. Таблица переходов-выходов автомата
| a(t-1) | 0 | 1 |
| a0 | a1/1 | a2/1 |
| a1 | a3/1 | a4/1 |
| a2 | a10/0 | a11/0 |
| a3 | - | a5/1 |
| a4 | - | a6/1 |
| a5 | a8/1 | a9/0 |
| a6 | a8/0 | - |
| a7 | a0/- | a0/- |
| a8 | a0/- | a0/- |
| a9 | a0/- | a0/- |
| a10 | - | a12/1 |
| a11 | a14/0 | a15/0 |
| a12 | a13/1 | - |
| a13 | a0/- | a0/- |
| a14 | - | a16/0 |
| a15 | a17/1 | a18/0 |
| a16 | a0/- | a0/- |
| a17 | a0/- | a0/- |
| a18 | a0/- | a0/- |
Один из алгоритмов минимизации полностью определенных автоматов заключается в следующем. Множество состояний исходного абстрактного автомата разбивается на попарно пересекающиеся классы эквивалентных состояний, далее каждый класс эквивалентности заменяется одним состоянием. В результате получается минимальный автомат, имеющий столько же состояний, на сколько классов эквивалентности разбиваются исходные состояния автомата.
0 класс эквивалентности:
| a0, a1 | b0 |
| a2, a11 | b1 |
| a14 | b2 |
| a3, a4, a10 | b3 |
| a5, a15 | b4 |
| a6 | b5 |
| a7, a8, a9, a13, a16, a17, a18 | b6 |
| a12 | b7 |
1 класс эквивалентности:
| a0 | c0 |
| a1 | c1 |
| a2 | c2 |
| a3 | c3 |
| a4 | c4 |
| a5, a15 | c5 |
| a6 | c6 |
| a10 | c7 |
| a11 | c8 |
| a12 | c9 |
| a14 | c10 |
| a7, a8, a9, a13, a16, a17, a18 | c11 |
2 класс эквивалентности:
| a0 | d0 |
| a1 | d1 |
| a2 | d2 |
| a3 | d3 |
| a4 | d4 |
| a5, a15 | d5 |
| a6 | d6 |
| a10 | d7 |
| a11 | d8 |
| a12 | d9 |
| a14 | d10 |
| a7, a8, a9, a13, a16, a17, a18 | d11 |
Из разбиения видно, что классы 1 и 2 совпадают, значит, продолжать не имеет смысла.
Таблица переходов-выходов минимизированного автомата представлена в таблице 4:
Таблица 4. Таблица переходов-выходов минимизированного автомата
| d(t-1) | 0 | 1 |
| d0 | d1/1 | d2/1 |
| d1 | d3/1 | d4/1 |
| d2 | d7/0 | d8/0 |
| d3 | - | d5/1 |
| d4 | - | d6/1 |
| d5 | d11/1 | d11/0 |
| d6 | d11/0 | - |
| d7 | - | d9/1 |
| d8 | d10/0 | d5/0 |
| d9 | d11/1 | - |
| d10 | - | d11/0 |
| d11 | d0/- | d0/- |
Граф переходов минимизированного автомата представлен в приложении 2.
2. СТРУКТУРНЫЙ СИНТЕЗ КОНЕЧНОГО АВТОМАТА
2.1 Кодирование состояний, входных и выходных сигналов
Для кодирования состояний, входных и выходных сигналов конечного автомата, необходимо вычислить число элементов памяти:
а) рассчитаем число элементов памяти: Н = ] log2h [, где h - число состояний после минимизации D = {
}
H = ] log2 12 [ = 4
б) рассчитаем число входных (L) и выходных (М) шин:
L = ] log2n[
М =] log2m [,
где n, m - число букв входного и выходного алфавитов
Z = {0, 1} L = ] log2 2 [ = 1
W = {0, 1} M = ] log2 2 [ = 1
Из приведённого выше следует, что для кодирования состояний необходимо 4 элемента памяти, обозначим их Q0, …, Q3. Закодируем состояния (таблица 5) случайными кодами.
Таблица 5. Таблица кодированных состояний
| d(t-1) | Q0 | Q1 | Q2 | Q3 |
| d0 | 0 | 0 | 0 | 0 |
| d1 | 0 | 0 | 0 | 1 |
| d2 | 0 | 0 | 1 | 0 |
| d3 | 0 | 0 | 1 | 1 |
| d4 | 0 | 1 | 0 | 0 |
| d5 | 0 | 1 | 0 | 1 |
| d6 | 0 | 1 | 1 | 0 |
| d7 | 0 | 1 | 1 | 1 |
| d8 | 1 | 0 | 0 | 0 |
| d9 | 1 | 0 | 0 | 1 |
| d10 | 1 | 0 | 1 | 0 |
| d11 | 1 | 0 | 1 | 1 |
Похожие работы
... состоянии am. Рассмотренные выше абстрактные автоматы можно разделить на: 1) полностью определенные и частичные; 2) детерминированные и вероятностные; 3) синхронные и асинхронные; Полностью определенным называется абстрактный цифровой автомат, у которого функция переходов и функция выходов определены для всех пар ( ai, zj). Частичным называется абстрактный автомат, у которого функция ...
... D=1- W3W4(W1W5W6+ W7+ W1W8+ W2W6 W7+ W2W7+2W2W8+ 1)+ W5W6(W3W4(W7+ W1W5W6+ W2W7+ W2W8+1)-1) Для x1 Для x4 Для y Для х13 Задание 2. Синтез комбинационных схем. 2.1 Определение поставленной задачи Устройство, работа которого может быть представлена на языке алгебры высказываний, принято называть логическим. Пусть такое устройство имеет n ...
... способ задания автомата. Рисунок № 1 Структурный синтез R =] log215 [=4 - количество элементов памяти L=] log24 [=2 - количество входных каналов N=] log26 [=3 - количество выходных каналов Синтез автомата Мили будем проводить на Т-триггерах. Т-триггер (триггер со счетным входом) имеет один вход. Он "переворачивается", изменяя свое состояние, каждый раз, когда на его вход поступает ...
... покажет уровень полученных нами знаний по курсу «Прикладная теория цифровых автоматов». Задание Выполнить синтез управляющего автомата операции умножения младшими разрядами вперед со сдвигом множимого над числами в форме с фиксированной точкой в формате {1,8}в прямом коде двоичной системы счисления. Разработать микропрограмму и выполнить синтез управляющего автомата используя синхронный ...
0 комментариев