Проектирование конечного автомата по алфавитному отображению

Размещено на 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.

2) Возводим нормализованную мантиссу числа W в квадрат, нормализуем и переведём двоичную систему счисления, 16 цифр после запятой полученной мантиссы записываем в виде столбца у2.

3) Для получения столбцов у3 и y4 мантисса десятичного числа возводится в третью и в четвёртую степени соответственно и переводится в двоичную систему счисления.

4) Полученный алфавитный оператор имеет вид, представленный в таблице 1.1

Построим по таблице 1.2 граф переходов автомата Мура. Будем при этом предполагать, что последний символ каждого входного слова должен переводит автомат в начальное состояние.

В момент времени t = 0 автомат находится в состоянии a₁. При подаче в последующие моменты времени каждого входного сигнала z(t) автомат переходит в новое состояние и вырабатывает выходной сигнал w(t).

Поскольку для абстрактного автомата порядок нумерации состояний, отличных от начального, безразличен, можно считать, что буква z(1) = 0 первого входного слова из таблицы 1.2 переводит автомат в состояние a₂. При этом вырабатывается выходной сигнал w(1) = ?. Буква z(2) = 0 переводит автомат из состояния a₂ в состояние a₃ и обеспечивает выработку выходного сигнала w(2) = ?. Буква z(3) = 0 переводит автомат из состояния a₃ в состояние a₄ и обеспечивает выработку выходного сигнала w(3) = ? и т.д. Последней в первом входном слове буквой z(7) = ? автомат должен переводиться в состояние a₁. Этому переходу соответствует выходной сигнал w(7) = 0. Начальные отрезки z(1)z(2)z(3), w(1)w(2)w(3) второго входного и выходного слов совпадают с соответствующими начальными отрезками первого входного и выходного слов, поэтому первые три перехода для второго входного слова совпадают с уже построенными. Последующие переходы для этого слова строятся точно так же, как и для первого слова. Затем строятся переходы для остальных входных и выходных слов. Граф переходов заданного автомата представлен на рисунке 1.1.

Таблица 1.2 Таблица переходов-выходов проектируемого автомата