Добавлен: 05.12.2023
Просмотров: 410
Скачиваний: 18
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
КУРСОВАЯ РАБОТАПО ДИСЦИПЛИНЕ ТЕОРИЯ АВТОМАТОВВВЕДЕНИЕТеория автоматов – это теория, на которой основаны экспериментальные методы исследования в кибернетике. При подходе к теории автоматов, как к части теории алгоритмов, центральной проблемой является изучение возможностей автоматов в терминах множеств слов, с которыми работают автоматы.Можно выделить два основных аспекта работы автомата.
Второе правило функционирования автоматов состоит в том, что на один и тот же входной сигнал конечный автомат может реагировать по-разному, в зависимости от того, в каком состоянии он находится в настоящий момент.Конечный автомат - это устройство, работающее в дискретные моменты времени, или такты. На вход конечного автомата в каждом такте поступает один из возможных входных сигналов, а на его выходе появляется выходной сигнал, являющийся функцией его текущего состояния и поступившего входного сигнала.Внутренние состояния автомата также меняются. Моменты срабатывания (такты), определяются либо принудительно тактирующими синхросигналами, либо асинхронно, наступлением внешнего события, то есть приходом сигнала.Существует два вида реализации конечного автомата - аппаратная и программная. В первую очередь, реализация конечного автомата требует построения устройства памяти для запоминания текущего состояния автомата. Обычно используются двоичные элементы памяти, или триггеры, запоминающие значение одного двоичного разряда.1. Цель и задачи курсовой работыВыполняя курсовую работу по теории автоматов и алгоритмов, студент приобретает навыки самостоятельного решения задач логического проектирования цифровых устройств. Эти задачи решаются комплексно, во взаимной увязке. Используется материал ранее изученных дисциплин (“Программирование и алгоритмизация”, “Информатика”, “Дискретная математика”). Главной задачей является логический синтез блока аппаратного управления специальным процессором.Выполнить синтез абстрактного автомата Мура по алгоритму в соответствии с вариантом и перевести автомат Мура в автомат Мили.Вариант 11. АБСТРАКТНЫЙ СИНТЕЗ КОНЕЧНОГО АВТОМАТА1.1 Формирование алфавитного оператораДля определения параметров задания необходимо ввести первичную информацию:- порядковый номер в журнале;- год поступления;- номер группы;Для данного задания это соответственно:
21, 08, 02.Из этих цифр необходимо составить правильную десятичную дробь, в которой эти цифры следуют сразу после запятой: Y1= 0,210802Вторичная информация Y ,Y3 ,Y4 получаются путем возведения 1 в степени 2, 3, 4 и удалением в дроби всех нулей между запятой и первой значимой цифрой.Y2 = 0,444374Y3 = 0,93675 Y4 = 0,19747Для получения значений входных и выходных сигналов автомата необходимо полученные десятичные дроби преобразовать в двоичный код до шестнадцатого знака.В результате преобразований получены следующие значения заданных сигналов.Y1 = 0011010111110111 Y2 = 0111000111000010Y3 = 1110111111001110Y4 = 0011001010001101Полученные значения записываются в столбцах: первые 8 значений в левой части, вторые 8 – в правой части. Алфавитный оператор соответствия представлен в таблице 1.Таблица 1. Алфавитный оператор соответствия
1.2 Приведение оператора к автоматному видуДля того чтобы оператор преобразовался к автоматному виду, необходимо выполнение трех условий:1. Любым двум одинаковым начальным отрезкам входных слов должны соответствовать одинаковые начальные отрезки выходных слов;2. Длина входного слова должна равняться длине выходного слова;3. Последний символ должен возвращать автомат в начальное состояние.Данный оператор уже выровнен, так как длина каждого из входных слов равна длине соответствующего выходного слова. Каждому входному слову здесь сопоставляются не более одного выходного слова, поэтому оператор однозначен. Однако он не удовлетворяет условию полноты.Таким образом, автоматный вид оператора примет, следующий вид: Таблица 2. Автоматный вид
1.3 Построение графа переходов абстрактного автоматаПостроим по таблице 2 граф переходов автомата. При этом предполагается, что последний символ каждого входного слова должен переводит автомат в начальное состояние.Граф переходов абстрактного автомата представлен в приложении 1.1.4 Минимизация абстрактного автоматаПо графу переходов построим таблицу переходов-выходов заданного автомата (таблица 3).Таблица 3. Таблица переходов-выходов автомата
Один из алгоритмов минимизации полностью определенных автоматов заключается в следующем. Множество состояний исходного абстрактного автомата разбивается на попарно пересекающиеся классы эквивалентных состояний, далее каждый класс эквивалентности заменяется одним состоянием. В результате получается минимальный автомат, имеющий столько же состояний, на сколько классов эквивалентности разбиваются исходные состояния автомата.0 класс эквивалентности:
1 класс эквивалентности:
2 класс эквивалентности:
-
Автоматы-распознаватели, которые распознают входные слова, т.е. отвечают на вопрос, принадлежит ли поданное на вход слово данному множеству. -
Автоматы-преобразователи, которые преобразуют входные слова в выходные, т.е. реализуют автоматные отображения.
Второе правило функционирования автоматов состоит в том, что на один и тот же входной сигнал конечный автомат может реагировать по-разному, в зависимости от того, в каком состоянии он находится в настоящий момент.Конечный автомат - это устройство, работающее в дискретные моменты времени, или такты. На вход конечного автомата в каждом такте поступает один из возможных входных сигналов, а на его выходе появляется выходной сигнал, являющийся функцией его текущего состояния и поступившего входного сигнала.Внутренние состояния автомата также меняются. Моменты срабатывания (такты), определяются либо принудительно тактирующими синхросигналами, либо асинхронно, наступлением внешнего события, то есть приходом сигнала.Существует два вида реализации конечного автомата - аппаратная и программная. В первую очередь, реализация конечного автомата требует построения устройства памяти для запоминания текущего состояния автомата. Обычно используются двоичные элементы памяти, или триггеры, запоминающие значение одного двоичного разряда.1. Цель и задачи курсовой работыВыполняя курсовую работу по теории автоматов и алгоритмов, студент приобретает навыки самостоятельного решения задач логического проектирования цифровых устройств. Эти задачи решаются комплексно, во взаимной увязке. Используется материал ранее изученных дисциплин (“Программирование и алгоритмизация”, “Информатика”, “Дискретная математика”). Главной задачей является логический синтез блока аппаратного управления специальным процессором.Выполнить синтез абстрактного автомата Мура по алгоритму в соответствии с вариантом и перевести автомат Мура в автомат Мили.Вариант 11. АБСТРАКТНЫЙ СИНТЕЗ КОНЕЧНОГО АВТОМАТА1.1 Формирование алфавитного оператораДля определения параметров задания необходимо ввести первичную информацию:- порядковый номер в журнале;- год поступления;- номер группы;Для данного задания это соответственно:
21, 08, 02.Из этих цифр необходимо составить правильную десятичную дробь, в которой эти цифры следуют сразу после запятой: Y1= 0,210802Вторичная информация Y ,Y3 ,Y4 получаются путем возведения 1 в степени 2, 3, 4 и удалением в дроби всех нулей между запятой и первой значимой цифрой.Y2 = 0,444374Y3 = 0,93675 Y4 = 0,19747Для получения значений входных и выходных сигналов автомата необходимо полученные десятичные дроби преобразовать в двоичный код до шестнадцатого знака.В результате преобразований получены следующие значения заданных сигналов.Y1 = 0011010111110111 Y2 = 0111000111000010Y3 = 1110111111001110Y4 = 0011001010001101Полученные значения записываются в столбцах: первые 8 значений в левой части, вторые 8 – в правой части. Алфавитный оператор соответствия представлен в таблице 1.Таблица 1. Алфавитный оператор соответствия
| Входные сигналы | Выходные сигналы |
| 0010 | 1111 |
| 0110 | 1110 |
| 1111 | 1000 |
| 1101 | 1000 |
| 0010 | 0011 |
| 1010 | 1011 |
| 0011 | 1110 |
| 1110 | 1001 |
1.2 Приведение оператора к автоматному видуДля того чтобы оператор преобразовался к автоматному виду, необходимо выполнение трех условий:1. Любым двум одинаковым начальным отрезкам входных слов должны соответствовать одинаковые начальные отрезки выходных слов;2. Длина входного слова должна равняться длине выходного слова;3. Последний символ должен возвращать автомат в начальное состояние.Данный оператор уже выровнен, так как длина каждого из входных слов равна длине соответствующего выходного слова. Каждому входному слову здесь сопоставляются не более одного выходного слова, поэтому оператор однозначен. Однако он не удовлетворяет условию полноты.Таким образом, автоматный вид оператора примет, следующий вид: Таблица 2. Автоматный вид
| Входные сигналы | Выходные сигналы |
| 0010 | 1111 |
| 0110 | 1110 |
| 1111 | 1000 |
| 1101 | 1000 |
| 00100000 | 11110011 |
| 1010 | 1011 |
| 0011 | 1110 |
| 1110 | 1001 |
| a(t-1) | 0 | 1 |
| a0 | a1/1 | a2/1 |
| a1 | a3/1 | a4/1 |
| a2 | a10/0 | a11/0 |
| a3 | - | a5/1 |
| a4 | - | a6/1 |
| a5 | a8/1 | a9/0 |
| a6 | a8/0 | - |
| a7 | a0/- | a0/- |
| a8 | a0/- | a0/- |
| a9 | a0/- | a0/- |
| a10 | - | a12/1 |
| a11 | a14/0 | a15/0 |
| a12 | a13/1 | - |
| a13 | a0/- | a0/- |
| a14 | - | a16/0 |
| a15 | a17/1 | a18/0 |
| a16 | a0/- | a0/- |
| a17 | a0/- | a0/- |
| a18 | a0/- | a0/- |
Один из алгоритмов минимизации полностью определенных автоматов заключается в следующем. Множество состояний исходного абстрактного автомата разбивается на попарно пересекающиеся классы эквивалентных состояний, далее каждый класс эквивалентности заменяется одним состоянием. В результате получается минимальный автомат, имеющий столько же состояний, на сколько классов эквивалентности разбиваются исходные состояния автомата.0 класс эквивалентности:
| a0, a1 | b0 |
| a2, a11 | b1 |
| a14 | b2 |
| a3, a4, a10 | b3 |
| a5, a15 | b4 |
| a6 | b5 |
| a7, a8, a9, a13, a16, a17, a18 | b6 |
| a12 | b7 |
| a0 | c0 |
| a1 | c1 |
| a2 | c2 |
| a3 | c3 |
| a4 | c4 |
| a5, a15 | c5 |
| a6 | c6 |
| a10 | c7 |
| a11 | c8 |
| a12 | c9 |
| a14 | c10 |
| a7, a8, a9, a13, a16, a17, a18 | c11 |
| a0 | d0 |
| a1 | d1 |
| a2 | d2 |
| a3 | d3 |
| a4 | d4 |
| a5, a15 | d5 |
| a6 | d6 |
| a10 | d7 |
| a11 | d8 |
| a12 | d9 |
| a14 | d10 |
| a7, a8, a9, a13, a16, a17, a18 | d11 |