Проектирование конечного автомата по алфавитному отображению
Способы проектирования конечного автомата по алфавитному отображению с использованием канонического метода структурного синтеза. Приведение алфавитного оператора к автоматному виду. Минимизация состояний абстрактного автомата. Оценка способов кодирования.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | курсовая работа |
| Язык | русский |
| Дата добавления | 07.08.2013 |
| Размер файла | 277,8 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Пояснительная записка к курсовому проекту
по дисциплине «Теория автоматов»
Проектирование конечного автомата по алфавитному отображению
Работу выполнил
Горелкин А.Е.
ВВЕДЕНИЕ
В данной работе выполняется проектирование конечного автомата по алфавитному отображению с использованием канонического метода структурного синтеза автоматов.
Теоретические основы канонического метода были разработаны В.М. Глушковым, сформулировавшим и доказавшим «теорему о структурной полноте».
Теорема о структурной полноте: всякая система элементарных автоматов, которая содержи автомат Мура, обладающий полной системой выходов, и какую-нибудь функционально полную систему логических элементов (элементарных автоматов без памяти), является структурно полной системой. Существует общий конструктивный приём, позволяющий свести задачу синтеза произвольных конечных автоматов к задаче структурного синтеза комбинационных схем.
На основании теоремы о структурной полноте структурная схема всякого автомата, синтезированного каноническим методом, будет состоять из двух частей: запоминающей части и комбинационной схемы. Запоминающая часть представляет собой совокупность элементарных автоматов Мура с полной системой переходов и выходов, а комбинационная часть представляет собой схему, построенную на постоянных запоминающих устройствах.
Структурный синтез автомата каноническим методом состоит из следующих этапов:
1. Кодирование состояний абстрактного автомата.
2. Кодирование абстрактных входных и выходных сигналов.
3. Составление кодированных таблиц переходов-выходов структурного автомата.
4. Формирование таблицы функций возбуждения структурного автомата.
5. Получение логических выражений функций возбуждения и выходных сигналов автомата.
6. Построение структурной схемы.
При кодировании состояний будет использован метод, называемый «кодирование, близкое к соседнему», позволяющий упростить полученную в результате структурного синтеза схему.
1. АБСТРАКТНЫЙ СИНТЕЗ КОНЕЧНОГО АВТОМАТА. ФОРМИРОВАНИЕ АЛФАВИТНОГО ОПЕРАТОРА
Алфавитное отображение формируется следующим образом.
На вход автомата поступают 16 различных последовательностей длины 4, составленных из букв двоичного алфавита {0,1}. На выходе вырабатывается 16 выходных последовательностей, составленных из букв того же алфавита.
По исходному числу W построим алфавитный оператор.
1) Исходное число W = 248441. Монтиссу этого числа нормализуем и записываем в двоичной системе счисления с точностью 16 разрядов, полученное число запишем в столбец y1.
|
y1 |
y2 |
y3 |
y4 |
|||||
|
1 |
1 |
1 |
1 |
|||||
|
0 |
1 |
0 |
0 |
|||||
|
1 |
1 |
0 |
1 |
|||||
|
0 |
0 |
1 |
0 |
|||||
|
1 |
1 |
1 |
0 |
|||||
|
1 |
0 |
1 |
0 |
|||||
|
0 |
0 |
0 |
1 |
|||||
|
0 |
1 |
1 |
0 |
|||||
|
1 |
0 |
0 |
0 |
|||||
|
0 |
0 |
1 |
0 |
|||||
|
1 |
0 |
0 |
0 |
|||||
|
1 |
1 |
0 |
1 |
|||||
|
1 |
1 |
1 |
0 |
|||||
|
1 |
0 |
0 |
1 |
|||||
|
0 |
1 |
1 |
1 |
|||||
|
0 |
0 |
0 |
0 |
2) Возводим нормализованную мантиссу числа W в квадрат, нормализуем и переведём двоичную систему счисления, 16 цифр после запятой полученной мантиссы записываем в виде столбца у2.
3) Для получения столбцов у3 и y4 мантисса десятичного числа возводится в третью и в четвёртую степени соответственно и переводится в двоичную систему счисления.
4) Полученный алфавитный оператор имеет вид, представленный в таблице 1.1
Таблица 1.1 Полученный алфавитный оператор
|
x1 |
x2 |
x3 |
x4 |
y1 |
y2 |
y3 |
y4 |
|
|
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
|
|
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
|
|
0 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
|
|
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
|
|
0 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
|
|
0 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
|
|
0 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
|
|
0 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
|
|
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
|
|
1 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
|
|
1 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
|
|
1 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
|
|
1 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
|
|
1 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
|
|
1 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
|
|
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
2. ПРИВЕДЕНИЕ АЛФАВИТНОГО ОПЕРАТОРА К АВТОМАТНОМУ ВИДУ
Данный оператор уже выровнен, так как длина каждого из входных слов равна длине соответствующего выходного слова. Каждому входному слову здесь сопоставляется не более одного выходного слова, поэтому оператор однозначен. Однако он не удовлетворяет условию полноты. Входной сигнал 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 |
3. ПОСТРОЕНИЕ ГРАФА ПЕРЕХОДОВ АБСТРАКТНОГО АВТОМАТА И ТАБЛИЦЫ ПЕРЕХОДОВ-ВЫХОДОВ
Построим по таблице 1.2 граф переходов автомата Мура. Будем при этом предполагать, что последний символ каждого входного слова должен переводит автомат в начальное состояние.
В момент времени t = 0 автомат находится в состоянии a1. При подаче в последующие моменты времени каждого входного сигнала z(t) автомат переходит в новое состояние и вырабатывает выходной сигнал w(t).
Поскольку для абстрактного автомата порядок нумерации состояний, отличных от начального, безразличен, можно считать, что буква z(1) = 0 первого входного слова из таблицы 1.2 переводит автомат в состояние a2. При этом вырабатывается выходной сигнал w(1) = ?. Буква z(2) = 0 переводит автомат из состояния a2 в состояние a3 и обеспечивает выработку выходного сигнала w(2) = ?. Буква z(3) = 0 переводит автомат из состояния a3 в состояние a4 и обеспечивает выработку выходного сигнала w(3) = ? и т.д. Последней в первом входном слове буквой z(7) = ? автомат должен переводиться в состояние a1. Этому переходу соответствует выходной сигнал w(7) = 0. Начальные отрезки z(1)z(2)z(3), w(1)w(2)w(3) второго входного и выходного слов совпадают с соответствующими начальными отрезками первого входного и выходного слов, поэтому первые три перехода для второго входного слова совпадают с уже построенными. Последующие переходы для этого слова строятся точно так же, как и для первого слова. Затем строятся переходы для остальных входных и выходных слов. Граф переходов заданного автомата представлен на рисунке 1.1.
Таблица 1.2 Таблица переходов-выходов проектируемого автомата
|
y |
a |
0 |
1 |
? |
|
|
0 |
a0' |
a1 |
a2 |
- |
|
|
1 |
a0” |
a1 |
a2 |
- |
|
|
в |
a1 |
a3 |
a4 |
- |
|
|
в |
a2 |
a5 |
a6 |
- |
|
|
в |
a3 |
a7 |
a8 |
- |
|
|
в |
a4 |
a9 |
a10 |
- |
|
|
в |
a5 |
a11 |
a12 |
- |
|
|
в |
a6 |
a13 |
a14 |
- |
|
|
в |
a7 |
a15 |
a16 |
- |
|
|
в |
a8 |
a17 |
a18 |
- |
|
|
1 |
a9 |
a19 |
a20 |
- |
|
|
0 |
a10 |
a21 |
a22 |
- |
|
|
в |
a11 |
a23 |
a24 |
- |
|
|
1 |
a12 |
a25 |
a26 |
- |
|
|
1 |
a13 |
a27 |
a28 |
- |
|
|
0 |
a14 |
a29 |
a30 |
- |
|
|
1 |
a15 |
- |
- |
a31 |
|
|
0 |
a16 |
- |
- |
a32 |
|
|
1 |
a17 |
- |
- |
a33 |
|
|
0 |
a18 |
- |
- |
a34 |
|
|
1 |
a19 |
- |
- |
a35 |
|
|
0 |
a20 |
- |
- |
a36 |
|
|
0 |
a21 |
- |
- |
a37 |
|
|
1 |
a22 |
- |
- |
a38 |
|
|
1 |
a23 |
- |
- |
a39 |
|
|
0 |
a24 |
- |
- |
a40 |
|
|
0 |
a25 |
- |
- |
a41 |
|
|
1 |
a26 |
- |
- |
a42 |
|
|
1 |
a27 |
- |
- |
a43 |
|
|
0 |
a28 |
- |
- |
a44 |
|
|
1 |
a29 |
- |
- |
a45 |
|
|
0 |
a30 |
- |
- |
a46 |
|
|
1 |
a31 |
- |
- |
a47 |
|
|
1 |
a32 |
- |
- |
а48 |
|
|
1 |
a33 |
- |
- |
а49 |
|
|
0 |
a34 |
- |
- |
а50 |
|
|
1 |
a35 |
- |
- |
a0' |
|
|
1 |
a36 |
- |
- |
a0' |
|
|
0 |
a37 |
- |
- |
a0” |
|
|
1 |
a38 |
- |
- |
a0' |
|
|
0 |
a39 |
- |
- |
а51 |
|
|
0 |
a40 |
- |
- |
а52 |
|
|
0 |
a41 |
- |
- |
a0' |
|
|
0 |
a42 |
- |
- |
a0” |
|
|
1 |
a43 |
- |
- |
a0' |
|
|
0 |
a44 |
- |
- |
a0” |
|
|
1 |
a45 |
- |
- |
a0” |
|
|
0 |
a46 |
- |
- |
a0' |
|
|
1 |
a47 |
- |
- |
a0” |
|
|
0 |
a48 |
- |
- |
a0' |
|
|
0 |
a49 |
- |
- |
a0” |
|
|
1 |
a50 |
- |
- |
a0' |
|
|
0 |
a51 |
- |
- |
a0' |
|
|
1 |
a52 |
- |
- |
a0' |
Таблица 1.3 Упрощенная таблица переходов-выходов проектируемого автомата
|
y |
A |
0 |
1 |
? |
|||||
|
0 |
b0' |
b1 |
b2 |
- |
b0' |
= |
a0' |
||
|
1 |
b0" |
b1 |
b2 |
- |
b0" |
= |
a0” |
||
|
В |
b1 |
b3 |
b4 |
- |
b1 |
= |
a1 |
||
|
В |
b2 |
b5 |
b6 |
- |
b2 |
= |
a2 |
||
|
В |
b3 |
b7 |
b8 |
- |
b3 |
= |
a3 |
||
|
В |
b4 |
b9 |
b10 |
- |
b4 |
= |
a4 |
||
|
В |
b5 |
b11 |
b12 |
- |
b5 |
= |
a5 |
||
|
В |
b6 |
b13 |
b14 |
- |
b6 |
= |
a6 |
||
|
B |
b7 |
b15 |
b16 |
- |
b7 |
= |
a7 |
||
|
B |
b8 |
b17 |
b18 |
- |
b8 |
= |
a8 |
||
|
1 |
b9 |
b19 |
b20 |
- |
b9 |
= |
a9 |
||
|
0 |
b10 |
b21 |
b22 |
- |
b10 |
= |
a10 |
||
|
B |
b11 |
b23 |
b24 |
- |
b11 |
= |
a11 |
||
|
1 |
b12 |
b25 |
b26 |
- |
b12 |
= |
a12 |
||
|
1 |
b13 |
b27 |
b28 |
- |
b13 |
= |
a13 |
||
|
0 |
b14 |
b29 |
b30 |
- |
b14 |
= |
a14 |
||
|
1 |
b15 |
- |
- |
b31 |
b15 |
= |
a15 |
||
|
0 |
b16 |
- |
- |
b32 |
b16 |
= |
a16 |
||
|
1 |
b17 |
- |
- |
b33 |
b17 |
= |
a17 |
||
|
0 |
b18 |
- |
- |
b34 |
b18 |
= |
a18 |
||
|
1 |
b19 |
- |
- |
B35 |
b19 |
= |
a19 |
||
|
0 |
b20 |
- |
- |
B35 |
b20 |
= |
a20 |
||
|
0 |
b21 |
- |
- |
b36 |
b21 |
= |
a21 |
||
|
1 |
b22 |
- |
- |
b35 |
b22 |
= |
a22 |
||
|
1 |
b23 |
- |
- |
b37 |
b23 |
= |
a23 |
||
|
0 |
b24 |
- |
- |
b38 |
b24 |
= |
a24 |
||
|
0 |
b25 |
- |
- |
B39 |
b25 |
= |
a25 |
||
|
1 |
b26 |
- |
- |
B36 |
b26 |
= |
a26 |
||
|
1 |
b27 |
- |
- |
B35 |
b27 |
= |
a27 |
||
|
0 |
b28 |
- |
- |
B36 |
b28 |
= |
a28 |
||
|
1 |
b29 |
- |
- |
B40 |
b29 |
= |
a29 |
||
|
0 |
b30 |
- |
- |
B39 |
b30 |
= |
a30 |
||
|
1 |
b31 |
- |
- |
B40 |
b31 |
= |
a31 |
||
|
1 |
b32 |
- |
- |
B36 |
b32 |
= |
a32 |
||
|
1 |
b33 |
- |
- |
B36 |
b33 |
= |
a33 |
||
|
0 |
b34 |
- |
- |
B35 |
b34 |
= |
a34 |
||
|
1 |
b35 |
- |
- |
b0' |
b35 |
= |
a35, a36, a38, a43, a50, a52 |
||
|
0 |
b36 |
- |
- |
b0'' |
b36 |
= |
a37, a 42, a44, a49 |
||
|
0 |
b37 |
- |
- |
b0' |
b37 |
= |
a39 |
||
|
1 |
b38 |
- |
- |
B0” |
b38 |
= |
a40 |
||
|
0 |
b39 |
- |
- |
b0' |
b39 |
= |
a41, a46, a 48, a51 |
||
|
1 |
b40 |
- |
- |
B0” |
b40 |
= |
a45, a47 |
Таблица 1.4 Упрощенная таблица переходов-выходов проектируемого автомата
|
y |
a |
0 |
1 |
? |
|||||
|
0 |
c0' |
c1 |
c2 |
- |
c0' |
= |
c0' |
||
|
1 |
c0" |
c1 |
c2 |
- |
c0" |
= |
b0” |
||
|
B |
c1 |
c3 |
c4 |
- |
c1 |
= |
b1 |
||
|
B |
c2 |
c5 |
c6 |
- |
c2 |
= |
b2 |
||
|
B |
c3 |
c7 |
c8 |
- |
c3 |
= |
b3 |
||
|
B |
c4 |
c9 |
c10 |
- |
c4 |
= |
b4 |
||
|
B |
c5 |
c11 |
c12 |
- |
c5 |
= |
b5 |
||
|
B |
c6 |
c13 |
c14 |
- |
c6 |
= |
b6 |
||
|
B |
c7 |
c15 |
c16 |
- |
c7 |
= |
b7 |
||
|
B |
c8 |
c17 |
c18 |
- |
c8 |
= |
b8 |
||
|
1 |
c9 |
c19 |
c20 |
- |
c9 |
= |
b9 |
||
|
0 |
c10 |
c21 |
c22 |
- |
c10 |
= |
b10 |
||
|
B |
c11 |
c23 |
c24 |
- |
c11 |
= |
b11 |
||
|
1 |
c12 |
c25 |
c26 |
- |
c12 |
= |
b12 |
||
|
1 |
c13 |
c27 |
c28 |
- |
c13 |
= |
b13 |
||
|
0 |
c14 |
c29 |
c30 |
- |
c14 |
= |
b14 |
||
|
1 |
c15 |
- |
- |
C0” |
c15 |
= |
b15 |
||
|
0 |
c16 |
- |
- |
C0' |
c16 |
= |
b16 |
||
|
0 |
c17 |
- |
- |
C0” |
c17 |
= |
b17 |
||
|
1 |
c18 |
- |
- |
c0' |
c18 |
= |
b18 |
||
|
1 |
c19 |
- |
- |
C0” |
c19 |
= |
b19, b22, b27 |
||
|
1 |
c20 |
- |
- |
C0” |
c20 |
= |
b20, b34 |
||
|
0 |
c21 |
- |
- |
C0” |
c21 |
= |
b21, b28 |
||
|
0 |
c22 |
- |
- |
C0' |
c22 |
= |
b23 |
||
|
1 |
c23 |
- |
- |
C0' |
c23 |
= |
b24 |
||
|
0 |
c24 |
- |
- |
C0' |
c24 |
= |
b25, b30 |
||
|
0 |
c25 |
- |
- |
C0” |
c25 |
= |
b26, b32, b33 |
||
|
1 |
c26 |
- |
- |
C0” |
c26 |
= |
b29, b 31 |
||
|
1 |
c27 |
- |
- |
c0' |
c27 |
= |
b35, b38 |
||
|
0 |
c28 |
- |
- |
C0” |
c28 |
= |
b36 |
||
|
0 |
c29 |
- |
- |
c0' |
c29 |
= |
b37, b39 |
||
|
1 |
c30 |
- |
- |
c0” |
c30 |
= |
b40 |
4. МИНИМИЗАЦИЯ СОСТОЯНИЙ АБСТРАКТНОГО АВТОМАТА
Продолжим минимизацию автомата с помощью метода треугольных таблиц. По таблице 1.4 составим треугольную таблицу совместимости состояний (таблица 1.5). Отметим все совместные и несовместные состояния.
Таблица 1.5 Треугольная таблица совместимости состояний
|
x |
|||||||||||||||||||||||||||||||
|
x |
x |
||||||||||||||||||||||||||||||
|
x |
x |
x |
|||||||||||||||||||||||||||||
|
x |
x |
x |
x |
||||||||||||||||||||||||||||
|
x |
x |
x |
x |
x |
|||||||||||||||||||||||||||
|
x |
x |
x |
x |
x |
x |
||||||||||||||||||||||||||
|
x |
x |
x |
x |
x |
x |
x |
|||||||||||||||||||||||||
|
x |
x |
x |
x |
x |
x |
x |
x |
||||||||||||||||||||||||
|
x |
x |
x |
x |
x |
x |
x |
x |
x |
|||||||||||||||||||||||
|
x |
x |
x |
x |
x |
x |
x |
x |
x |
x |
||||||||||||||||||||||
|
x |
x |
x |
x |
x |
x |
x |
x |
x |
x |
x |
|||||||||||||||||||||
|
x |
x |
x |
x |
x |
x |
x |
x |
x |
x |
x |
x |
||||||||||||||||||||
|
x |
x |
x |
x |
x |
x |
x |
x |
x |
x |
x |
x |
x |
|||||||||||||||||||
|
x |
x |
x |
x |
x |
x |
x |
x |
x |
x |
x |
x |
x |
x |
||||||||||||||||||
|
x |
x |
x |
x |
x |
x |
x |
x |
x |
x |
x |
x |
x |
x |
x |
|||||||||||||||||
|
x |
v |
x |
x |
x |
x |
x |
x |
x |
x |
v |
x |
x |
v |
v |
x |
||||||||||||||||
|
v |
x |
x |
x |
x |
x |
x |
x |
x |
x |
x |
v |
x |
x |
x |
v |
x |
|||||||||||||||
|
v |
x |
x |
x |
x |
x |
x |
x |
x |
x |
x |
v |
x |
x |
x |
v |
x |
x |
||||||||||||||
|
x |
v |
x |
x |
x |
x |
x |
x |
x |
x |
v |
x |
x |
v |
v |
x |
x |
x |
x |
|||||||||||||
|
x |
v |
x |
x |
x |
x |
x |
x |
x |
x |
v |
x |
x |
v |
v |
x |
x |
x |
x |
v |
||||||||||||
|
x |
v |
x |
x |
x |
x |
x |
x |
x |
x |
v |
x |
x |
v |
v |
x |
x |
x |
x |
v |
v |
|||||||||||
|
v |
x |
x |
x |
x |
x |
x |
x |
x |
x |
x |
v |
x |
x |
x |
v |
x |
x |
v |
x |
x |
x |
||||||||||
|
v |
x |
x |
x |
x |
x |
x |
x |
x |
x |
x |
v |
x |
x |
x |
v |
x |
v |
x |
x |
x |
x |
x |
|||||||||
|
x |
v |
x |
x |
x |
x |
x |
x |
x |
x |
v |
x |
x |
v |
v |
x |
x |
x |
x |
v |
v |
v |
x |
x |
||||||||
|
v |
x |
x |
x |
x |
x |
x |
x |
x |
x |
x |
v |
x |
x |
x |
v |
x |
v |
x |
x |
x |
x |
x |
v |
x |
|||||||
|
v |
x |
x |
x |
x |
x |
x |
x |
x |
x |
x |
v |
x |
x |
x |
v |
x |
x |
v |
x |
x |
x |
v |
x |
x |
x |
||||||
|
x |
v |
x |
x |
x |
x |
x |
x |
x |
x |
v |
x |
x |
v |
v |
x |
v |
x |
x |
x |
x |
x |
x |
x |
x |
x |
x |
|||||
|
x |
v |
x |
x |
x |
x |
x |
x |
x |
x |
v |
x |
x |
v |
v |
x |
x |
x |
x |
v |
v |
v |
x |
x |
v |
x |
x |
x |
||||
|
v |
x |
x |
x |
x |
x |
x |
x |
x |
x |
x |
v |
x |
x |
x |
v |
x |
x |
v |
x |
x |
x |
v |
x |
x |
x |
v |
x |
x |
|||
|
v |
x |
x |
x |
x |
x |
x |
x |
x |
x |
x |
v |
x |
x |
x |
v |
x |
v |
x |
x |
x |
x |
x |
Подобные документы
Изучение методов построения конечного автомата, распознающего заданный язык, и принципы его программной реализации. Проектирование комбинационной и принципиальной схем распознающего конечного автомата с использованием библиотеки интегральных микросхем.
дипломная работа [1,8 M], добавлен 18.08.2013Методика минимизации абстрактного автомата. Порядок построения графа полученного минимизированного автомата. Синтез на элементах ИЛИ-НЕ и Т-тригерах. Составление таблицы переходов. Разработка микропрограммного автомата, реализующего микропрограмму.
курсовая работа [997,7 K], добавлен 28.03.2011Синтез автомата для преобразования двоично-десятичного кода. Кодировка алфавитов и состояний. Построение булевых функций, минимизация. Разметка вход-выходных слов для автомата Мили и автомата Мура. Реализация на элементах малой степени интеграции.
контрольная работа [141,5 K], добавлен 14.10.2012Минимизация абстрактного автомата Мили, моделирование его работы. Синтез схемы конечного автомата, микропрограммного автомата и счетчика числа микрокоманд. Разработка цифровой линии задержки. Построение граф-схем исходного и оптимизированного автоматов.
курсовая работа [823,8 K], добавлен 19.07.2012Построение праволинейной грамматики, автоматной грамматики по полученным результатам. Построение недетерминированного конечного автомата. Сведение недетерминированного конечного автомата к детерминированному. Описание программы и контрольного примера.
курсовая работа [674,9 K], добавлен 13.06.2012Составление формальной грамматики, недетерминированный конечный автомат. Построение конечного автомата, программное моделирование работы конечного автомата. Граф детерминированного автомата, Синтаксическая диаграмма. Блок-схемы, примеры разбора строк.
курсовая работа [486,2 K], добавлен 19.11.2010Разработка управляющего автомата, ориентированного на выполнение заданной микрооперации. Разработка алгоритма работы управляющего автомата. Листинг программы. Выбор оптимального варианта кодирования состояний автомата. Синтез функции возбуждения.
курсовая работа [506,9 K], добавлен 26.12.2012Важный частный случай недетерминированного конечного автомата. Проверка нечетности числа единиц в произвольной цепочке, состоящей из нулей и единиц. Составление формальной грамматики, блок-схемы и программы, моделирующей работу конечного автомата.
курсовая работа [210,8 K], добавлен 05.12.2013Устройство управления и синхронизации в структуре микропроцессора. Порядок синтеза конечного автомата (КА) для устройства управления ЭВМ. Алгоритм функционирования КА, заданный с помощью графа, функции переходов. Состояние триггеров в микросхеме.
методичка [1019,0 K], добавлен 28.04.2009Сведение недетерминированного конечного автомата к детерминированному. Построение минимального детерминированного автомата из праволинейной грамматики двумя различными способами: с помощью сетей Петри и с помощью таблиц. Описание контрольного примера.
курсовая работа [903,9 K], добавлен 14.07.2012Составление треугольной таблицы. Нахождение списка максимальных классов совместимости, минимального замкнутого покрытия. Получение логических функций выходов автомата. Синтез конечного автомата и функциональной схемы. Принципиальная электрическая схема.
контрольная работа [215,8 K], добавлен 22.06.2012Понятие, последовательность построения и схемная реализация цифрового автомата. Описание форм представления функций алгебры логики. Принципы минимизации функций выходов и переходов автомата, их перевода в базис. Сведенья о программе Electronics Workbench.
курсовая работа [2,0 M], добавлен 27.10.2010Содержание и особенности этапов синтеза дискретного автомата. Граф переходов-выходов автомата Мура, кодирование входных и выходных сигналов. Построение функциональной схемы автомата Мура на RS–триггерах и элементах И-НЕ в программе Electronic WorkBench.
курсовая работа [964,2 K], добавлен 20.07.2015Разработка управляющего автомата процессора с жесткой логикой в САПР Quartus II. Построение схемы функциональной микропрограммы команды "Исключающее ИЛИ" в размеченном виде. Унитарное кодирование состояний автомата. Запись функций переходов и выходов.
курсовая работа [671,3 K], добавлен 04.11.2014Проект цифрового устройства для передачи сообщения через канал связи. Разработка задающего генератора, делителя частоты, преобразователя кода, согласующего устройства с каналом связи, схемы синхронизации и сброса, блока питания; оптимизация автомата.
курсовая работа [3,4 M], добавлен 05.02.2013Синтез цифрового автомата с комбинационной частью на логических элементах. Реализация спроектированного автомата в виде иерархического блока со схемой замещения на библиотечных компонентах в режиме SPICE–проектов. Разработка абстрактных символов.
курсовая работа [831,2 K], добавлен 23.09.2013Оптимізація схеми мікропрограмного автомата Мура за рахунок нестандартного подання кодів станів. Аналіз методів синтезу автомата та аналіз сучасного елементного базису. Використанні особливостей автомата для зменшення площини матричної схеми автомата.
презентация [357,0 K], добавлен 16.10.2013Разработка функциональной схемы управляющего микропрограммного автомата. Построение графов автомата для модели Мили и Мура. Кодирование состояний для модели Мура на D-триггерах. Алгоритм умножения чисел в дополнительном коде с простой коррекцией.
курсовая работа [764,0 K], добавлен 27.08.2012Построение математической модели программы, одноленточного автомата над алфавитом, допускающего различные множества слов. Алфавит терминальных символов, множество состояний и переходов. Определение начального и конечного состояний. Понятие сети Петри.
контрольная работа [294,8 K], добавлен 17.09.2013Общая схема D-триггера и цифрового автомата Мили. Построение входных и выходных преобразователей в соответствии с таблицами кодирования входных и выходных сигналов. Составление таблиц переходов и выхода состояния автомата Мили. Выбор серии микросхем.
курсовая работа [525,4 K], добавлен 04.11.2012
