Проектирование конечного автомата по алфавитному отображению с использованием канонического метода структурного синтеза автоматов
Этапы структурного синтеза автомата каноническим методом. Построение графа переходов абстрактного автомата и таблицы переходов-выходов. Использование тактирования от генератора синхронизирующих импульсов для устранения гонок в функциональной схеме.
Рубрика | Производство и технологии |
Вид | курсовая работа |
Язык | русский |
Дата добавления | 21.02.2016 |
Размер файла | 1,5 M |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Проектирование конечного автомата по алфавитному отображению с использованием канонического метода структурного синтеза автоматов
Введение
В данной работе будет представлено проектирование конечного автомата по алфавитному отображению с использованием канонического метода структурного синтеза автоматов.
На основании теоремы о структурной полноте структурная схема всякого автомата, синтезированного каноническим методом, будет состоять из двух частей: запоминающей части и комбинационной схемы. Запоминающая часть представляет собой совокупность элементарных автоматов Мура с полной системой переходов и выходов, а комбинационная часть представляет собой схему, построенную из логических элементов, составляющих функционально полный базис.
Структурный синтез автомата каноническим методом состоит из следующих этапов:
Кодирование состояний абстрактного автомата.
Кодирование абстрактных входных и выходных сигналов.
Составление кодированных таблиц переходов-выходов структурного автомата.
Формирование таблицы функций возбуждения структурного автомата.
Получение логических выражений функций возбуждения и выходных сигналов автомата.
Построение структурной схемы.
При кодировании состояний будет использован метод, называемый «кодирование случайными кодами», позволяющий упростить полученную в результате структурного синтеза схему.
По исходному числу W построим алфавитный оператор, который представлен в таблице 1.1
Исходное число W = 0,24042. Для получения столбца w(n) необходимо возвести число W в n-ую степень. При необходимости нормализовать полученное число (после запятой первая действующая цифра отличная от нуля).
Нормализованное число W запишем в двоичной системе счисления с точностью 16 разрядов. Правила перевода дробных чисел из десятичной системы счисления в двоичную:
- вначале переводится целая часть десятичной дроби в двоичную систему счисления;
- затем дробная часть десятичной дроби умножается на основание двоичной системы счисления;
- в полученном произведении выделяется целая часть, которая принимается в качестве значения первого после запятой разряда числа в двоичной системе счисления;
- алгоритм завершается, если дробная часть полученного произведения равна нулю или если достигнута требуемая точность вычислений. В противном случае вычисления продолжаются с предыдущего шага.
Полученное число запишем в столбец w(n).
Ниже представлено формирование столбцов алфавитного оператора:
Формирование столбца w(1)
По заданию W^1=0,174042. Осуществим его перевод в двоичную систему счисления. Для этого исходная дробь умножается на основание системы счисления, в которую переводится; в полученном произведении целая часть преобразуется в соответствии с таблицей в цифру нужной системы счисления и отбрасывается - она является старшей цифрой получаемой дроби; оставшаяся дробная часть вновь умножается на нужное основание системы счисления с последующей обработкой полученного произведения в соответствии с шагами.
Произведем перевод числа 0,174042 в двоичный код:
1) 0,174042*2=0,348084 0
2) 0,348084*2=0,696168 0
3) 0,696168*2=1,392336 1
4) 0,392336*2=0,784672 0
5) 0,784672*2=1,569344 1
6) 0,569344*2=1,138688 1
7) 0,138688*2=0,277376 0
8) 0,277376*2=0,554752 0
9) 0,554752*2=1,109504 1
10) 0,109504*2=0,219008 0
11) 0,219008*2=0,438016 0
12) 0, 438016*2=0,876032 0
13) 0, 876032*2=1,752064 1
14) 0,752064*2=1,504128 1
15) 0,504128*2=1,008256 1
16) 0,008256*2=0,016512 0
w(1)=0,0010110010001110
2) Формирование столбца w(2)
Нормализованная мантисса числа W возводится в квадрат, нормализуется и переводится в двоичную систему, переведенное 16-разрядное число записывается в столбец W2;
W2 = (0,174042)2
Нормализованный вид числа - 0,30290617.
Произведем перевод числа 0,30290617 в двоичный код:
0,30290617*2=0,60581234 0
0,60581234*2=1,21162468 1
0,21162468*2=0,42324936 0
0,42324936*2=0,84649872 0
0,84649872*2=1,69299744 1
0,69299744*2=1,38599488 1
0,38599488*2= 0,77198976 0
0,77198976 *2=1,54397952 1
1,54397952*2= 1,08795904 1
0,08795904*2= 0,17591808 0
0,17591808*2= 0,35183616 0
0,35183616*2= 0,70367232 0
0,70367232*2= 1,40734464 1
0,40734464*2= 0,81468928 0
0,81468928*2= 1,62937856 1
0, 62937856*2=1,25875712 1
w(2)=0,0100110110001011
3) Формирование столбца w(3)
Нормализованная мантисса числа W возводится в куб, нормализуется и переводится в двоичную систему, переведенное 16-разрядное число записывается в столбец W3;
W3 = (0,174042)3
Нормализованный вид полученного числа - 0,5271839
Произведем перевод числа 0,5271839 в двоичный код:
0,5271839 *2=1,0543678 1
0,0543678*2=0,1087356 0
0,1087356*2=0,2174712 0
0,2174712 *2=0,4349424 0
0,4349424 *2=0,8698848 0
0,8698848 *2=1,7397696 1
0,7397696*2=1,4795392 1
0, 4795392*2=0,9590784 0
0,9590784 *2=1,9181568 1
0, 9181568*2=1,8363136 1
0,8363136*2=1,6726272 1
0,6726272*2=1,3452544 1
0,3452544*2=0,6905088 0
0,6905088*2=1,3810176 1
0,3810176*2=0,7620352 0
0,7620352*2=1,5240704 1
w(3)=0,1000011011110101
4) Формирование столбца w(4)
Нормализованная мантисса числа W возводится в четвертую степень, нормализуется и переводится в двоичную систему, переведенное 16-разрядное число записывается в столбец W4.
W4 = (0,174042)4
Нормализованный вид полученного числа - 0,917521
Произведем перевод числа 0,917521 в двоичный код:
0,917521 *2=1,835042 1
0,835042*2=1,670084 1
0,670084*2=1,340168 1
0,340168*2=0,680336 0
0, 680336*2=1,360672 1
0,360672*2=0,721344 0
0,721344*2=1,442688 1
0,442688*2=0,885376 0
0,885376 *2=1,770752 1
0,770752*2=1,541504 1
0,541504*2=1,083008 1
0,083008*2=0,166016 0
0,166016*2=0,332032 0
0,332032*2=0,664064 0
0,664064 *2=1,328128 1
0,328128*2=0,656256 0
w(4)=0,1110101011100010
1. Абстрактный синтез конечного автомата. Алфавитный оператор
На вход автомата поступают 16 различных последовательностей длины 4, составленных из букв двоичного алфавита {0,1}. На выходе вырабатывается 16 выходных последовательностей, составленных из букв того же алфавита.
Алфавитный оператор представлен в таблице 1.1.
Таблица 1.1.- Алфавитный оператор
Входные сигналы |
Выходные сигналы |
||||||||
Z1 |
Z2 |
Z3 |
Z4 |
W1 |
W2 |
W3 |
W4 |
||
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
|
1 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
|
2 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
|
3 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
|
4 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
|
5 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
|
6 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
|
7 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
|
8 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
|
9 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
|
10 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
|
11 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
|
12 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
|
13 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
|
14 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
|
15 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
1.2 Приведение оператора соответствия к автоматному виду
Правила формирования данного оператора:
- длины входных и выходных последовательностей должны быть одинаковы:
- на одинаковые начальные участки входных последовательностей, автомат должен отвечать формированием одинаковых начальных участков выходных последовательностей:
- приведение автомата к стандартному виду осуществляется путем использования пустых символов: - входной пустой символ, - выходной пустой символ.
В результате получена таблица 1.2.
Таблица 1.2. - Автоматный оператор соответствия
Входные сигналы |
Выходные сигналы |
||||||||||||||
Z1 |
Z2 |
Z3 |
Z4 |
W1 |
W2 |
W3 |
W4 |
||||||||
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
|||||||
1 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
|||||||
2 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
|||||||
3 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
|||||||
4 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
|||||||
5 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
|||||||
6 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
|||||||
7 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
|||||||
8 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
|||||||
9 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
|||||||
10 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
|||||||
11 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
|||||||
12 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
|||||||
13 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
|||||||
14 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
|||||||
15 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
1.3 Построение графа переходов абстрактного автомата и таблицы переходов-выходов
Граф переходов автомата Мура строится на основе таблицы 1.2. При этом предполагается, что последний символ каждого входного слова должен переводит автомат в начальное состояние.
В момент времени t = 0 автомат находится в состоянии а0. При подаче в последующие моменты времени каждого входного сигнала z(t) автомат вырабатывает выходной сигнал w(t) и переходит в новое состояние. Порядок нумерации состояний, отличных от начального состояния, для абстрактного автомата безразличен.
Для примера, рассмотрим первую строчку в таблице 1.2. Под воздействием нуля автомат переходит из а0 в а1 и вырабатывает сигнал в. Под воздействием второго нуля автомат из а1 переходит в а3 и вырабатывает сигнал в. Под воздействием третьего нуля автомат из а3 переходит в а5 и вырабатывает сигнал 0. Под воздействием четвертого нуля автомат из а5 переходит в а6 и вырабатывает сигнал 0. Далее под воздействием первого б автомат из а6 переходит в а7 и вырабатывает сигнал 1. Под воздействием второго б автомат из а7 переходит снова в а0 и вырабатывает сигнал 1. Рассуждая аналогичным образом можно построить остальные ветки графа.
Граф переходов заданного автомата представлен на рисунке 1.
Рисунок 1. - Граф переходов автомата Мура.
На основе полученного графа построим таблицу переходов-выходов.
Таблица 1.3. - Таблица переходов-выходов состояния «а»
0 |
1 |
б |
|||
0 |
a'0 |
a1 |
a2 |
- |
|
1 |
a''0 |
a1 |
a2 |
- |
|
в |
a1 |
a3 |
a4 |
- |
|
в |
a2 |
a27 |
a40 |
- |
|
в |
a3 |
a5 |
a10 |
- |
|
в |
a4 |
a17 |
a22 |
- |
|
0 |
a5 |
a6 |
a8 |
- |
|
0 |
a6 |
- |
- |
a7 |
|
1 |
a7 |
- |
- |
a''0 |
|
1 |
a8 |
- |
- |
a9 |
|
0 |
a9 |
- |
- |
a''0 |
|
в |
a10 |
a11 |
a14 |
- |
|
1 |
a11 |
- |
- |
a12 |
|
0 |
a12 |
- |
- |
a13 |
|
0 |
a13 |
- |
- |
a''0 |
|
0 |
a14 |
- |
- |
a15 |
|
0 |
a15 |
- |
- |
a16 |
|
0 |
a16 |
- |
- |
a'0 |
|
1 |
a17 |
a18 |
a20 |
- |
|
1 |
a18 |
- |
- |
a19 |
|
0 |
a19 |
- |
- |
a''0 |
|
1 |
a20 |
- |
- |
a21 |
|
1 |
a21 |
- |
- |
a'0 |
|
0 |
a22 |
a23 |
a25 |
- |
|
0 |
a23 |
- |
- |
a24 |
|
1 |
a24 |
- |
- |
a''0 |
|
1 |
a25 |
- |
- |
a26 |
|
0 |
a26 |
- |
- |
a'0 |
|
в |
a27 |
a28 |
a35 |
- |
|
в |
a28 |
a29 |
a32 |
- |
|
1 |
a29 |
- |
- |
a30 |
|
1 |
a30 |
- |
- |
a31 |
|
1 |
a31 |
- |
- |
a''0 |
|
0 |
a32 |
- |
- |
a33 |
|
0 |
a33 |
- |
- |
a34 |
|
1 |
a34 |
- |
- |
a''0 |
|
0 |
a35 |
a36 |
a38 |
- |
|
0 |
a36 |
- |
- |
a37 |
|
1 |
a37 |
- |
- |
a''0 |
|
0 |
a38 |
- |
- |
a39 |
|
1 |
a39 |
- |
- |
a'0 |
|
в |
a40 |
a41 |
a46 |
- |
|
1 |
a41 |
a42 |
a44 |
- |
|
1 |
a42 |
- |
- |
a43 |
|
0 |
a43 |
- |
- |
a'0 |
|
0 |
a44 |
- |
- |
a45 |
|
1 |
a45 |
- |
- |
a'0 |
|
в |
a46 |
a47 |
a50 |
- |
|
1 |
a47 |
- |
- |
a48 |
|
1 |
a48 |
- |
- |
a49 |
|
0 |
a49 |
- |
- |
a''0 |
|
0 |
a50 |
- |
- |
a51 |
|
1 |
a51 |
- |
- |
a52 |
|
1 |
a52 |
- |
- |
a'0 |
|
1.4 Минимизация состояний автомата
Минимизация числа состояний выполняется в два этапа. На этапе первичной минимизации необходимо найти и объединить в одно все состояния, имеющие одинаковые выходные символы и при переходе вырабатывающие одинаковые состояния. Второй этап минимизации проводится с помощью треугольной таблицы.
1.4.1 Первичная минимизация
Как видно из таблицы 1.3 состояния а7, а24, а31, а34 и а31 под воздействием б переходят в a''0 и вырабатывают 1, следовательно, их можно объединить в одну группу. Рассуждения аналогичны и для остальных состояний.
Обозначим получившиеся состояния буквой «в» и перепишем таблицу переходов-выходов:
в'0 = a'0 |
в11= a11 |
в23= a27 |
в35= a44 |
|
в'0 = a''0 |
в12= a12 |
в24= a28 |
в36= a46 |
|
в1= a1 |
в13= a14 |
в25= a29 |
в37= a47 |
|
в2= a2 |
в14= a15 |
в26= a30 |
в38= a48 |
|
в3= a3 |
в15= (a16; a26; a43) |
в27= a32 |
в39= a50 |
|
в4= a4 |
в16= a17 |
в28= a33 |
в30= a51 |
|
в5= a5 |
в17= a18 |
в29= a35 |
||
в6= a6 |
в18= a20 |
в30= a36 |
||
в7= (a7; a24; a31; a34; a37) |
в19= (a21; a31; a45; a52) |
в31= a38 |
||
в8= a8 |
в20= a22 |
в32= a40 |
||
в8= (a9; a13; a19; a49) |
в21= a23 |
в33= a41 |
||
в10= a10 |
в22= a25 |
в34= a42 |
Таблица 1.4. - Таблица переходов-выходов состояния «в».
0 |
1 |
б |
|||
0 |
в'0 |
в1 |
в2 |
- |
|
1 |
в''0 |
в1 |
в2 |
- |
|
в |
в1 |
в3 |
в4 |
- |
|
в |
в2 |
в23 |
в32 |
- |
|
в |
в3 |
в5 |
в10 |
- |
|
в |
в4 |
в16 |
в20 |
- |
|
0 |
в5 |
в6 |
в8 |
- |
|
0 |
в6 |
- |
- |
в7 |
|
1 |
в7 |
- |
- |
в''0 |
|
1 |
в8 |
- |
- |
в9 |
|
0 |
в9 |
- |
- |
в''0 |
|
в |
в10 |
в11 |
в13 |
- |
|
1 |
в11 |
- |
- |
в12 |
|
0 |
в12 |
- |
- |
в9 |
|
0 |
в13 |
- |
- |
в14 |
|
0 |
в14 |
- |
- |
в15 |
|
0 |
в15 |
- |
- |
в'0 |
|
1 |
в16 |
в17 |
в18 |
- |
|
1 |
в17 |
- |
- |
в9 |
|
1 |
в18 |
- |
- |
в19 |
|
1 |
в19 |
- |
- |
в'0 |
|
0 |
в20 |
в21 |
в22 |
- |
|
0 |
в21 |
- |
- |
в7 |
|
1 |
в22 |
- |
- |
в15 |
|
в |
в23 |
в24 |
в29 |
- |
|
в |
в24 |
в25 |
в27 |
- |
|
1 |
в25 |
- |
- |
в26 |
|
1 |
в26 |
- |
- |
в7 |
|
0 |
в27 |
- |
- |
в28 |
|
0 |
в28 |
- |
- |
в7 |
|
0 |
в29 |
в30 |
в31 |
- |
|
0 |
в30 |
- |
- |
в7 |
|
0 |
в31 |
- |
- |
в19 |
|
в |
в32 |
в33 |
в36 |
- |
|
1 |
в33 |
в34 |
в35 |
- |
|
1 |
в34 |
- |
- |
в15 |
|
0 |
в35 |
- |
- |
в19 |
|
в |
в36 |
в37 |
в39 |
- |
|
1 |
в37 |
- |
- |
в38 |
|
1 |
в38 |
- |
- |
в39 |
|
0 |
в39 |
- |
- |
в40 |
|
1 |
в40 |
- |
- |
в19 |
Как видно таблица 1.4 не является окончательной, и минимизацию можно продолжить. Обозначим получившиеся состояния буквой «с» и перепишем таблицу переходов-выходов:
c'0= в'0 |
c11= в11 |
c23= в25 |
|
c''0= в''0 |
c12= в12 |
c24= в26 |
|
c1= в1 |
c13= в13 |
c25= в27 |
|
c2= в2 |
c14= в14 |
c26= в29 |
|
c3= в3 |
c15= в15 |
c27= (в31; в35) |
|
c4= в4 |
c16= в16 |
c28= в32 |
|
c5= в5 |
c17= (в18; в40) |
c29= в33 |
|
c6= (в6; в21; в28; в30) |
c18= в19 |
c30= в36 |
|
c7= в7 |
c19= в20 |
c31= в37 |
|
c8= (в8; в17; в38) |
c20= (в22; в34) |
c32= в39 |
|
c9= в9 |
c21= в23 |
||
c10= в10 |
c22= в24 |
Таблица 1.5. - Таблица переходов-выходов состояния «c».
0 |
1 |
б |
|||
0 |
c'0 |
c1 |
c2 |
- |
|
1 |
c''0 |
c1 |
c2 |
- |
|
в |
c1 |
c3 |
c4 |
- |
|
в |
c2 |
c21 |
c28 |
- |
|
в |
c3 |
c5 |
c10 |
- |
|
в |
c4 |
c16 |
c19 |
- |
|
0 |
c5 |
c6 |
c8 |
- |
|
0 |
c6 |
- |
- |
c7 |
|
1 |
c7 |
- |
- |
c''0 |
|
1 |
c8 |
- |
- |
c9 |
|
0 |
c9 |
- |
- |
c''0 |
|
в |
c10 |
c11 |
c13 |
- |
|
1 |
c11 |
- |
- |
c12 |
|
0 |
c12 |
- |
- |
c9 |
|
0 |
c13 |
- |
- |
c14 |
|
0 |
c14 |
- |
- |
c15 |
|
0 |
c15 |
- |
- |
c'0 |
|
1 |
c16 |
c8 |
c17 |
- |
|
1 |
c17 |
- |
- |
с18 |
|
1 |
c18 |
- |
- |
c'0 |
|
0 |
c19 |
c6 |
c10 |
- |
|
1 |
c20 |
- |
- |
c15 |
|
в |
c21 |
c22 |
c26 |
- |
|
в |
c22 |
c23 |
c25 |
- |
|
1 |
c23 |
- |
- |
c24 |
|
1 |
c24 |
- |
- |
c7 |
|
0 |
c25 |
- |
- |
c6 |
|
0 |
c26 |
c6 |
c27 |
- |
|
0 |
c27 |
- |
- |
c18 |
|
в |
c28 |
c29 |
c30 |
- |
|
1 |
c29 |
c20 |
c27 |
- |
|
в |
c30 |
c31 |
c32 |
- |
|
1 |
c31 |
- |
- |
c8 |
|
0 |
c32 |
- |
- |
c17 |
Теперь можно перейти к следующему этапу - минимизации с помощью треугольной таблицы.
1.4.2 Минимизация с помощью треугольной таблицы
Составим треугольную таблицу (рисунок 2), руководствуясь следующими правилами:
1) строки таблицы обозначаются состояниями c1, c2, …, cn-1, а столбцы c0, c1, …, cn-2, где n - число состояний абстрактного автомата;
2) на пересечении i-той строки и j-того столбца записываются условия, при которых возможно объединение состояний ci и cj; если состояния нельзя объединить ни при каких условиях, ставится знак «х»; если они объединяются, безусловно, то ставится знак «v»; окончательное объединение состояний определяется на основе непротиворечивости условий.
Рисунок 2. Минимизация с помощью треугольной матрицы
Выпишем из таблицы пары эквивалентных состояний:
(0?, 6) |
(0??, 7) |
(4, 10) |
(5, 6) |
(6, 9) |
(7, 16) |
(8, 16) |
(9, 19) |
(11,16) |
(12,15) |
(13,14) |
|
(0?, 9) |
(0??, 8) |
(4, 22) |
(5, 9) |
(6, 19) |
(7, 17) |
(8, 18) |
(9, 26) |
(11,18) |
(12,19) |
(13,15) |
|
(0?, 12) |
(0??, 11) |
(4, 30) |
(5, 12) |
(6, 26) |
(7, 23) |
(8, 29) |
(9, 27) |
(11,20) |
(12,25) |
(13,19) |
|
(0?, 13) |
(0??, 17) |
(5, 13) |
(6, 32) |
(7, 24) |
(9, 32) |
(11,29) |
(12,26) |
(13,26) |
|||
(0?, 14) |
(0??, 18) |
(5, 14) |
(7, 29) |
||||||||
(0?, 15) |
(0??, 20) |
(5, 15) |
(7, 31) |
||||||||
(0?, 25) |
(0??, 23) |
(5, 25) |
|||||||||
(0?, 27) |
(0??, 24) |
(5, 27) |
|||||||||
(0?, 32) |
(0??, 31) |
(5, 32) |
(14, 15) |
(15, 19) |
(16, 17) |
(17, 29) |
(18, 20) |
(19, 25) |
(20,29) |
(23,24) |
(24,29) |
(25,26) |
|
(14, 19) |
(15, 25) |
(16, 18) |
(17, 30) |
(18, 29) |
(19, 27) |
(23,29) |
||||
(14, 26) |
(15, 26) |
(16, 20) |
(19, 32) |
|||||||
(16, 23) |
||||||||||
(16, 24) |
||||||||||
(16, 31) |
(26, 27) |
(29, 31) |
|||||||||
(26, 32) |
Исходя из треугольной матрицы, получим следующие эквивалентных состояний, обозначенные буквой «d»:
d'0 = (0', 9)
d''0 = (0'', 7, 23, 24)
d1 = (1)
d2 = (2)
d3 = (3)
d4 = (4)
d5 = (5, 6)
d6 = (8, 16, 18)
d7 = (10)
d8 = (11, 20, 29)
d9 = (12, 15)
d10 = (17, 31)
d11 = (19, 25)
d12 = (26, 27)
d13 = (28)
d14 = (30)
d15 = (32)
d16 = (29)
d17 = (21)
d18 = (13)
d19 = (14)
d20 = (22)
Полученные эквивалентные состояния полностью удовлетворяют условиям замкнутости и полноты.
На основе полученных пар получаем таблицу переходов-выходов минимального автомата (таблица 1.6).
Таблица 1.6 - Таблица переходов-выходов минимального автомата
0 |
1 |
б |
|||
0 |
d' |
d1 |
d1 |
d''0 |
|
1 |
d''0 |
d1 |
d2 |
d''0 |
|
в |
d1 |
d3 |
d4 |
- |
|
в |
d2 |
d17 |
d13 |
- |
|
в |
d3 |
d5 |
d7 |
- |
|
в |
d4 |
d6 |
d11 |
- |
|
0 |
d5 |
d5 |
d6 |
d''0 |
|
1 |
d6 |
d6 |
d10 |
d'0 |
|
в |
d7 |
d8 |
d18 |
- |
|
1 |
d8 |
d8 |
d12 |
d9 |
|
0 |
d9 |
- |
- |
d'0 |
|
1 |
d10 |
- |
- |
d6 |
|
0 |
d11 |
d5 |
d8 |
d5 |
|
0 |
d12 |
d5 |
d12 |
d6 |
|
в |
d13 |
d16 |
d14 |
- |
|
в |
d14 |
d10 |
d15 |
- |
|
0 |
d15 |
- |
- |
d10 |
|
1 |
d16 |
d8 |
d12 |
- |
|
в |
d17 |
d20 |
d12 |
- |
|