Материалы представленные на сайте исключительно с целью ознакомления пользователям Интернета и не преследуют коммерческих целей или нарушение авторских прав.
© 2018 - 2024
Для определения параметров задания необходимо ввести первичную информацию:
- порядковый номер в журнале;
- год поступления;
- номер группы;
Для данного задания это соответственно:
21, 08, 02.
Из этих цифр необходимо составить правильную десятичную дробь, в которой эти цифры следуют сразу после запятой:
Y1= 0,210802
Вторичная информация Y,Y3 ,Y4 получаются путем возведения 1 в степени 2, 3, 4 и удалением в дроби всех нулей между запятой и первой значимой цифрой.
Y2 = 0,444374
Y3 = 0,93675
Y4 = 0,19747
Для получения значений входных и выходных сигналов автомата необходимо полученные десятичные дроби преобразовать в двоичный код до шестнадцатого знака.
В результате преобразований получены следующие значения заданных сигналов.
Y1 = 0011010111110111
Y2 = 0111000111000010
Y3 = 1110111111001110
Y4 = 0011001010001101
Полученные значения записываются в столбцах: первые 8 значений в левой части, вторые 8 – в правой части. Алфавитный оператор соответствия представлен в таблице 1.
Таблица 1. Алфавитный оператор соответствия
| Входные сигналы | Выходные сигналы |
| 0010 | 1111 |
| 0110 | 1110 |
| 1111 | 1000 |
| 1101 | 1000 |
| 0010 | 0011 |
| 1010 | 1011 |
| 0011 | 1110 |
| 1110 | 1001 |
Приведение оператора к автоматному виду
Для того чтобы оператор преобразовался к автоматному виду, необходимо выполнение трех условий:
1. Любым двум одинаковым начальным отрезкам входных слов должны соответствовать одинаковые начальные отрезки выходных слов;
2. Длина входного слова должна равняться длине выходного слова;
3. Последний символ должен возвращать автомат в начальное состояние.
Данный оператор уже выровнен, так как длина каждого из входных слов равна длине соответствующего выходного слова. Каждому входному слову здесь сопоставляются не более одного выходного слова, поэтому оператор однозначен. Однако он не удовлетворяет условию полноты.
Таким образом, автоматный вид оператора примет, следующий вид:
Таблица 2. Автоматный вид
| Входные сигналы | Выходные сигналы |
| 0010 | 1111 |
| 0110 | 1110 |
| 1111 | 1000 |
| 1101 | 1000 |
| 00100000 | 11110011 |
| 1010 | 1011 |
| 0011 | 1110 |
| 1110 | 1001 |
Построение графа переходов абстрактного автомата
Построим по таблице 2 граф переходов автомата. При этом предполагается, что последний символ каждого входного слова должен переводит автомат в начальное состояние.
Граф переходов абстрактного автомата представлен в приложении 1.
Минимизация абстрактного автомата
По графу переходов построим таблицу переходов-выходов заданного автомата (таблица 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.
С ТРУКТУРНЫЙ СИНТЕЗ КОНЕЧНОГО АВТОМАТА
Дата: 2019-05-28, просмотров: 205.