- •Кп 44.230101.В8441.Пз
- •Гкнт рф санкт-петербургский государственный университет аэрокосмического приборостроения
- •Техническое задание по курсовому проектированию на тему: «Проектирование конечного автомата по алфавитному отображению»
- •Технические условия
- •Содержание пояснительной записки
- •Введение
- •Абстрактный синтез конечного автомата
- •Формирование алфавитного оператора
- •Для получения столбцов у3 и y4 мантисса десятичного числа возводится в третью и в четвёртую степени соответственно и переводится в двоичную систему счисления.
- •Приведение алфавитного оператора к автоматному виду
- •Построение графа переходов абстрактного автомата и таблицы переходов-выходов
- •Минимизация состояний абстрактного автомата
- •Кодирование автомата
- •2.3 Разработка функциональной схемы структурного автомата
- •Заключение
Приведение алфавитного оператора к автоматному виду
Данный оператор уже выровнен, так как длина каждого из входных слов равна длине соответствующего выходного слова. Каждому входному слову здесь сопоставляется не более одного выходного слова, поэтому оператор однозначен. Однако он не удовлетворяет условию полноты. Входной сигнал x1 = 0 для первого, третьего, шестого, седьмого и восьмого слова w(1) = 0, а для третьего, четвертого, седьмого слов w(1) = 1. По этой причине оператор неоднозначен для начальных отрезков слов. Проведём пополнение заданного оператора.
Поскольку, для приведения алфавитного оператора к автоматному виду мы используем символы и , то можем применить экономную процедуру выравнивания. Поскольку в таблице 1.1 при z(1) = 0 для первого, второго, третьего, шестого и восьмого слова w(1) = 0, а для третьего, четвертого, седьмого слов w(1) = 1, допишем к входным словам справа , а к выходным словам слева по одному . Далее в таблице 1.1 при z(1) = 1 для десятого, пятнадцатого и шестнадцатого слов w(1) = 0, а для остальных w(1) = 1. Поэтому допишем справа к вторым восьми словам , а слева . Если при этом считать, что z(1) преобразуется в 0, то для однобуквенных начальных отрезков слов получилось однозначное преобразование.
Рассмотрим двухбуквенные начальные отрезки входных слов. Поскольку комбинация z(1)z(2) = 00 преобразуется неоднозначно, а именно для первого, второго и третьего слов w(1)w(2) = 00, а для четвертого w(1)w(2) = 11, то допишем к первым четырем входным словам справа , а к выходным словам слева . Проделаем подобную процедуру для всех начальных отрезков длины 2 символа. Далее рассмотрим трёхбуквенные начальные отрезки входных слов и повторим процедуру пополнения. Четырёхбуквенные начальные отрезки входных слов все различны, поэтому они преобразуются однозначно.
В результате операции пополнения получена таблица 1.2.
Таблица 1.2
Полученный автоматный оператор
|
z(1) |
z(2) |
z(3) |
z(4) |
z(5) |
z(6) |
z(7) |
w(1) |
w(2) |
w(3) |
w(4) |
w(5) |
w(6) |
w(7) |
|
0 |
0 |
0 |
0 |
|
|
|
b |
b |
b |
1 |
1 |
1 |
1 |
|
0 |
0 |
0 |
1 |
|
|
|
b |
b |
b |
0 |
1 |
0 |
0 |
|
0 |
0 |
1 |
0 |
|
|
|
b |
b |
b |
1 |
1 |
0 |
1 |
|
0 |
0 |
1 |
1 |
|
|
|
b |
b |
b |
0 |
0 |
1 |
0 |
|
0 |
1 |
0 |
0 |
|
|
|
|
b |
b |
1 |
1 |
1 |
0 |
|
0 |
1 |
0 |
1 |
|
|
|
|
b |
b |
1 |
0 |
1 |
0 |
|
0 |
1 |
1 |
0 |
|
|
|
|
b |
b |
0 |
0 |
0 |
1 |
|
0 |
1 |
1 |
1 |
|
|
|
|
b |
b |
0 |
1 |
1 |
0 |
|
1 |
0 |
0 |
0 |
|
|
|
b |
b |
b |
1 |
0 |
0 |
0 |
|
1 |
0 |
0 |
1 |
|
|
|
b |
b |
b |
0 |
0 |
1 |
0 |
|
1 |
0 |
1 |
0 |
|
|
|
|
b |
b |
1 |
0 |
0 |
0 |
|
1 |
0 |
1 |
1 |
|
|
|
|
b |
b |
1 |
1 |
0 |
1 |
|
1 |
1 |
0 |
0 |
|
|
|
|
b |
b |
1 |
1 |
1 |
0 |
|
1 |
1 |
0 |
1 |
|
|
|
|
b |
b |
1 |
0 |
0 |
1 |
|
1 |
1 |
1 |
0 |
|
|
|
|
b |
b |
0 |
1 |
1 |
1 |
|
1 |
1 |
1 |
1 |
|
|
|
|
b |
b |
0 |
0 |
0 |
0 |