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

Пояснительная записка к курсовому проекту по дисциплине «Теория автоматов»В данной работе выполняется проектирование конечного автомата по алфавитному отображению с использованием канонического метода структурного синтеза автоматов. Теорема о структурной полноте: всякая система элементарных автоматов, которая содержи автомат Мура, обладающий полной системой выходов, и какую-нибудь функционально полную систему логических элементов (элементарных автоматов без памяти), является структурно полной системой. Существует общий конструктивный прием, позволяющий свести задачу синтеза произвольных конечных автоматов к задаче структурного синтеза комбинационных схем. На основании теоремы о структурной полноте структурная схема всякого автомата, синтезированного каноническим методом, будет состоять из двух частей: запоминающей части и комбинационной схемы. Запоминающая часть представляет собой совокупность элементарных автоматов Мура с полной системой переходов и выходов, а комбинационная часть представляет собой схему, построенную на постоянных запоминающих устройствах.Данный оператор уже выровнен, так как длина каждого из входных слов равна длине соответствующего выходного слова. Каждому входному слову здесь сопоставляется не более одного выходного слова, поэтому оператор однозначен. Поскольку в таблице 1.1 при z(1) = 0 для первого, второго, третьего, шестого и восьмого слова w(1) = 0, а для третьего, четвертого, седьмого слов w(1) = 1, допишем к входным словам справа ?, а к выходным словам слева по одному ?. Если при этом считать, что z(1) преобразуется в 0, то для однобуквенных начальных отрезков слов получилось однозначное преобразование. Поскольку комбинация z(1)z(2) = 00 преобразуется неоднозначно, а именно для первого, второго и третьего слов w(1)w(2) = 00, а для четвертого w(1)w(2) = 11, то допишем к первым четырем входным словам справа ?, а к выходным словам слева ?.Будем при этом предполагать, что последний символ каждого входного слова должен переводит автомат в начальное состояние. При подаче в последующие моменты времени каждого входного сигнала z(t) автомат переходит в новое состояние и вырабатывает выходной сигнал w(t). Поскольку для абстрактного автомата порядок нумерации состояний, отличных от начального, безразличен, можно считать, что буква z(1) = 0 первого входного слова из таблицы 1.2 переводит автомат в состояние a2. Буква z(2) = 0 переводит автомат из состояния a2 в состояние a3 и обеспечивает выработку выходного сигнала w(2) = ?. Буква z(3) = 0 переводит автомат из состояния a3 в состояние a4 и обеспечивает выработку выходного сигнала w(3) = ? и т.д.Продолжим минимизацию автомата с помощью метода треугольных таблиц. По таблице 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 v x v 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 c01 c0"" c1 c2 c3 c4 c5 c6 c7 c8 c9 c10 c11 c12 c13 c14 c15 c16 c17 c18 c19 c20 c21 c22 c23 c24 c25 c26 c27 c28 c29 Таблица 1.7Таблица переходов-выходовминимального автомата y d 0 1 dРезультатом выполнения данной курсовой работы является конечный минимальный структурный автомат, построенный на основе алфавитного отображения и готовый к работе. В ходе работы над полученным заданием мною были применены на практике все навыки, полученные во время слушания курса «Теория автоматов».