Методы анализа и синтеза конечных автоматов на структурном уровне
Примеры применения операций над автоматами. Методы нахождения объединения, пересечения, произведения и суммы автоматов. Составление автоматной таблицы и матрицы соединений по отображениям. Синтез комбинационного автомата, реализующего булеву формулу.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | лабораторная работа |
| Язык | русский |
| Дата добавления | 06.02.2019 |
| Размер файла | 97,2 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Федеральное агентство образования
ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР)
Кафедра компьютерных систем в управлении и проектировании (КСУП)
Лабораторная работа
«МАТЕМАТИЧЕСКИЕ ОСНОВЫ ТЕОРИИ СИСТЕМ»
Автор учебно-методического пособия: А.Г. Карпов
автомат матрица булевый
Юрга 2008
Цель лабораторной работы - потренироваться в применении операций над автоматами и освоить некоторые методы анализа и синтеза конечных автоматов на структурном уровне.
Заданы автоматы А и В. Найти их объединение и пересечение.
A B
объединение . пересечение
Заданы автоматы А и В. Найти автомат С = А В, равный их произведению.
A B
Входной алфавит автомата С - это упорядоченные пары входных букв автоматов А и В: обозначим их где
Выходной алфавит автомата С обозначим через , где
Алфавит состояний автомата С - это
, , , .
По полученным отображениям можно составить автоматную таблицу:
и матрицу соединений RC:
RC
Эту же матрицу соединений можно получить и из матриц соединений автоматов А и В путем прямого умножения этих матриц:
RA RB
RC
Заданы автоматы А и В. Найти автомат С = А В, равный их произведению.
А В
Автомат будет иметь алфавит состояний ,,,
и выходной алфавит , , , , .
С = А В
После подстановки введенных обозначений, произведение С = А В будет выглядеть:
С = А В
Заданы автоматы А и В. Найти их сумму А + В.
A B
Входные, и выходные алфавиты автоматов А и В не пересекаются. Поэтому входной алфавит и выходной алфавит . Алфавит состояний
,
где .
Отображение Rh1 по входной букве x1, т.е. функция перехода . Поскольку состояние h1 есть пара (q1,w1), а входная буква принадлежит алфавиту X автомата А, то =
Отображение Rh1 по входной букве x2, т.е. функция перехода =(2,1)=h3, а функция выхода равна C(q1,x2)=y1
Отображение Rh1 по входной букве u1, т.е. функция перехода =(2,1)= .
Отображение Rh1 по входной букве u2, т.е. функция перехода =(1,1)=h1, а функция выхода равна C(q1,u2)=v2.
Окончательно получим:
По полученным отображениям составляем автоматную таблицу C=A+B и матрицу соединений RC:
C
RC
Заданы автоматы А и В. Найти их суперпозицию А В.
A B
Входной алфавит автомата N совпадает со входным алфавитом автомата А: , а выходной алфавит - с выходным алфавитом автомата В: . Алфавит состояний, как и во всех алгебраических операциях - это
, .
Состояние h1 автомата N соответствует состоянию q1 автомата А и состоянию w1 автомата В. По входной букве x1 состояние автомата А не определено. По входной букве x2 автомат А переходит из состояния 1 в состояние 2 с выходом y1, но отображение состояния 1 автомата В по этой букве не определено, Таким образом, получаем:
Автоматная таблица, составленная по этим отображениям:
N=A*B
Вероятностные автоматы без выходов А = (X, Q, q1 Q, P) и
B = (Y, V, v1 V, S), X = {x1, x2}, Q = {q1, q2}, Р , Y = {y1, y2} V = {v1, v2}, S,
заданы своими стохастическими матрицами P и S. Найти вероятностные автоматы, равные их произведению и сумме.
Найдем автомат . Входной алфавит Z и алфавит состояний W автомата С, согласно формулам Z=XY, W=QV, будут равны
Стохастические матрицы автомата С найдем по формуле R=PS, прямым произведением соответствующих матриц автоматов А и В.
Найдем автомат . Для определения входного алфавита автомата D=A+B пользуемся формулой Z=XY . По формуле R=(PEB)(EAS) находим стохастические матрицы автомата D.
7. В заданном базисе синтезировать комбинационный автомат, реализующий булеву формулу F. Результат представить в виде структурной схемы.
Базис ДНФ. .
рис. 1
8. Написать бинарную программу, реализующую комбинационный автомат, вычисляющий формулу F для задания № 7. Результат представить в виде графа программы.
.
Рис. 2
Вывод: в ходе выполнения лабораторной работы были получены навыки в применении операций над автоматами и освоены некоторые методы анализа и синтеза конечных автоматов на структурном уровне.
Размещено на Allbest.ru
...Подобные документы
Понятие автомата как дискретного преобразователя информации, особенности его состояний. Синтез конечных автоматов, их задания и структурных анализ. Построение синтеза функций возбуждения элементарных автоматов. Комбинационный синтез конечных автоматов.
курсовая работа [336,4 K], добавлен 01.06.2014Составление треугольной таблицы. Нахождение списка максимальных классов совместимости, минимального замкнутого покрытия. Получение логических функций выходов автомата. Синтез конечного автомата и функциональной схемы. Принципиальная электрическая схема.
контрольная работа [215,8 K], добавлен 22.06.2012Теоретические основы эквивалентности конечных автоматов-распознавателей и их минимизация. Определение математических моделей Мили и Мура. Их графическое и табличное представление. Примеры построения конечных автоматов, распознающих некоторые языки.
курсовая работа [567,8 K], добавлен 02.05.2015Синтез и детерминизация, алгоритм минимизации автоматов–распознавателей. Машина Тьюринга как универсальный тип абстрактного преобразователя. Моделирование систем и событий с помощью сетей Петри. Методы синтеза структурных автоматов на базе триггеров.
учебное пособие [2,3 M], добавлен 17.06.2014Теоретические и практические основы грамматик, теория конечных автоматов-распознавателей. Эквивалентные и недостижимые состояния конечных автоматов. Классификация грамматик и порождаемых ими языков. Разработка программного комплекса построения грамматик.
курсовая работа [654,2 K], добавлен 14.11.2010Основные понятия структурных автоматов. Этапы канонического метода синтеза. Кодирование алфавитов автомата и выбор элементов его памяти. Построение уравнений булевых функций возбуждения и выходов. Методы устранения гонок в структурных автоматах.
курсовая работа [496,3 K], добавлен 27.01.2011Методика минимизации абстрактного автомата. Порядок построения графа полученного минимизированного автомата. Синтез на элементах ИЛИ-НЕ и Т-тригерах. Составление таблицы переходов. Разработка микропрограммного автомата, реализующего микропрограмму.
курсовая работа [997,7 K], добавлен 28.03.2011Построим содержательные графы выполнения трёх команд языка Ассемблера. Команда умножения двоичных чисел без знака mul. Команда преобразования типов cwde. Логическая команда xor. Синтез канонического автомата. Синтез М-автомата. Управляющие сигналы.
реферат [35,7 K], добавлен 18.11.2004В статье рассмотрено применение конечных автоматов для создания системы автоматов, связанных графами. Документооборот представляется в виде автомата, обрабатывающего автоматы, каждый из которых моделирует поведенческую единицу системы документооборота.
статья [80,8 K], добавлен 19.04.2006Принципы и понятия автоматного программирования. Виды конечных автоматов, их применение при построении лексических и синтаксических анализаторов. Описание конечных автоматов Миля и Мура, их различий в зависимости от способа формирования функций выхода.
курсовая работа [430,9 K], добавлен 26.05.2015В статье рассмотрено применение конечных автоматов для создания системы автоматов, связанных графами. Документооборот представляется в виде автомата, обрабатывающего автоматы, каждый из которых моделирует поведенческую единицу системы документооборота.
статья [80,8 K], добавлен 15.07.2006Минимизация абстрактного автомата Мили, моделирование его работы. Синтез схемы конечного автомата, микропрограммного автомата и счетчика числа микрокоманд. Разработка цифровой линии задержки. Построение граф-схем исходного и оптимизированного автоматов.
курсовая работа [823,8 K], добавлен 19.07.2012Структура блока обработки данных, синтез операционного и управляющего автоматов с микропрограммируемой логикой в структурном базисе комплекта 1804. Разработка алгоритма регенерации динамического ЗУ, особенности интерфейса шины процессор – память ISA.
курсовая работа [3,3 M], добавлен 23.12.2014Основное направление исследования клеточных автоматов. Математическое определение автоматов. Классификация по типам поведения. Тоталистичные клеточные автоматы. Создание и визуализация в Excel математической модели распространения лесного пожара.
курсовая работа [234,9 K], добавлен 01.11.2014Синтез контролирующих опросных циклических реляторных автоматов. Организация структуры с приоритетной стратегией "дейзи-цепочка", "дейзи-кольцо". Элементарный логический реляторный процессор. Сущность приоритетной перестраиваемой реляторной структуры.
контрольная работа [479,5 K], добавлен 20.03.2016Алгоритм умножения двоичных чисел. Выбор и описание структурной схемы операционного автомата. Реализация содержательной граф-схемы алгоритма. Построение отмеченной граф-схемы и структурной таблицы переходов и выходов. Правила кодирования на D-триггерах.
курсовая работа [273,2 K], добавлен 01.04.2013Понятие и свойства конечного автомата, его назначение и сферы применения. порядок разработки специальной функции, реализующей конечный автомат. Способы описания данной функции, обоснование выбора одного из них. Программная реализация решения задачи.
курсовая работа [466,4 K], добавлен 20.01.2010Рассмотрение методов совершения основных операций (содержания, равенства, пересечения, объединения, разности, произведения, отрицания и дизъюнктивной суммы) над нечеткими множествами, их функциональных моделей и программной реализации решения задачи.
курсовая работа [486,8 K], добавлен 25.01.2010Построение праволинейной грамматики, автоматной грамматики по полученным результатам. Построение недетерминированного конечного автомата. Сведение недетерминированного конечного автомата к детерминированному. Описание программы и контрольного примера.
курсовая работа [674,9 K], добавлен 13.06.2012Синтез автомата для преобразования двоично-десятичного кода. Кодировка алфавитов и состояний. Построение булевых функций, минимизация. Разметка вход-выходных слов для автомата Мили и автомата Мура. Реализация на элементах малой степени интеграции.
контрольная работа [141,5 K], добавлен 14.10.2012
