- •Теория автоматов. Уровни представления эвм.
- •Операционные элементы. (оэ)
- •Процессор гса:
- •Достоинства и недостатки.
- •Операционное устройство для выполнения операций алгебраического сложения двоичных чисел.
- •Суммирование при использовании прямого кодирования.
- •Суммирование чисел при использовании обратного кода.
- •Дополнительный код.
- •Модифицированный код.
- •Пример суммирования.
- •Конечные автоматы.
- •Теория конечных автоматов
- •Способы задания функций переходов.
- •Автоматы ( с выходным преобразователем)
- •Способы задания автоматов
- •Способы задания автомата Миля
- •Преобразование автоматов из Миля в Мура и обратно Понятие эквивалентности автоматов
- •Преобразование Мура в Миля
- •Техника преобразований.
- •Обратный переход. Построение Мура для заданного Миля.
- •Частичные или не полностью определенные автоматы.
- •Синтез конечных автоматов.
- •Абстрактный синтез конечных автоматов.
- •Построение дерева входных последовательностей.
- •Структурный этап синтеза автоматов.
- •Основные этапы структурного синтеза.
- •Типы памяти.
- •Основные типы триггеров.
- •Пример структурного синтеза синхронного автомата.
- •`Временная диаграмма.
- •Этап минимизации автомата при абстрактном синтезе. Минимизация полностью определенного автомата.
- •Алгоритмы минимизации на основе треугольной матрицы.
- •Минимизация числа состояний частичного автомата.
- •Минимизация частичного автомата.
- •Абстрактный этап синтеза конечного автомат. (неканонический метод).
- •Алгоритм перехода от граф схемы микропрограммы к автомату Мура.
- •Учет взаимодействия проекционного и управляющего автоматов. Алгоритм получения.
- •Алгоритм получения частичного автомата.
- •Множество входных значений.
- •Кодирование состояний синхронного автомата.
- •Кодирование соседними кодами.
- •Минимизация числа переключений элементов памяти.
- •Универсальный способ кодирования (для синхронного автомата).
- •Автомат с дешифратором.
- •Асинхронные автоматы.
- •Этапы синтеза асинхронного автомата.
- •Реализация асинхронного rs триггера на логических элементах.
- •Установочные входы в триггерах.
- •Синхронные элементы памяти.
- •Требования, предъявляемые к синхросигналу.
- •Синтез синхронного rs триггера.
- •Синтез триггера с задержкой.Реализация асинхронного t триггера.
- •Исключение состязаний элементов памяти в синхронных автоматах.
- •Структура автоматов на плм и пзу.
- •Явление рисков в комбинационных узлах.
- •Исключение влияние рисков.
- •Построение схем без риска.
- •Алгоритм построения схемы без рисков по днф.
- •Алгоритм построения схемы без риска.
- •Автоматы, языки и грамматики.
- •Задача распознавания цепочек языка.
- •Классификация грамматик по Хомскому.
- •Примеры построения грамматик.
- •Грамматика для выполнения арифметических операций.
- •Соответствие конечных автоматов и автоматных грамматик.
- •Этапы для заданной автоматной грамматики.
- •Этапы для заданной автоматной грамматики.
- •Недетерминированные конечные автоматы.
- •Преобразование недетерминированного автомата в детерминированный.
- •Преобразование некоторых типов грамматики к автоматному ввиду.
- •Алгоритм получения правил, не содержащих правил вывода нетерминальных символов.
- •Построение распознавателей и преобразователей.
- •Построение распознавателей.
- •Алгоритм построения преобразователя.
Преобразование Мура в Миля
Ar = <Pr , Wr , Sr , s0r , φr , ψr>
Al = <Pl , Wl , Sl , s0l , φl , ψl>
Ar– автомат Мура задан, необходимо найти эквивалентное ему автомат Миля.Al
Pl = Pr
Wl = Wr
Sl = Sr
В общем случае число соответствий Миля может оказаться меньше чем число соответствий Мура, следовательно
Sl <= Sr
s0l = s0r
в Мура Sr(t+1) = φr(Sr(t) , Pr(t))
в Миле Sl(t+1) = φl(Sr(t) , Pl(t))
следовательно φl(SiPj) =φ(SjPj)
Новое состояние как в Муре так и в Миле зависит от предыдущего состояния и предыдущего входного сигнала.
Так как во время преобразования Мура в Миля уже установлены условия 1 и 3, то функция переходов при одном и том же воздействии автомата Миля должна совпадать с функцией переходов автомата Мура при тех же воздействиях.
Wl(t+1) = ψl(Sl(t) , Pl(t))
Wr(t+1) = ψr(Sr(t+1)) = ψr(φr(Sr(t) , Pr(t))
Wl(t+1) = Wr(t+1)
В автомате Миля новое выходное значение зависит от старых состояний и выходного сигнала.
В автомате Мура выходной сигнал зависит от нового состояния, т.к. новое состояние
Sr(t+1) = φr (Sr(t) , Pr(t))
Определяется через старое состояние, то подставим
Sr(t+1).
Сравнивая функции выходов автомата Миля и Мура видно, что для обеспечения условий необходимо выходные значения автомата Мура соответствующие новым состояниям, сделать равным выходным значениям автомата Миля полученным на преходах в это состояние.
Техника преобразований.
При преобразовании автомата Мура в Миля необходимо выходные символы, которыми помечены вершины перенести на все входящие дуги в данную вершину.
Пример :
А
P2
S1/W2
P2
Si/
*
S2/W1
P1
P1
P2
Автомат Миля
P2/W1
S0
P2/W2
S1
S2
P1/W2
P1/W2
P2/W1
Обратный переход. Построение Мура для заданного Миля.
Пример
Si
Sj
Pk/Wk
т.е. нужно получить :
Si
Sj/Pk
Pk
Пример 2 :
Si
Sj
Sk
Sl
Sm
Pi
/ Wi
Pj
/ Wj
Pk
/ Wk
Pm
/ Wm
тогда происходит расщепление состояний :
Sj
Sl/Wi
Pm
Sj
Sl
Sl/Wj
Sl/Wl
Sm/Wk
Pm
Pm
При переходе от автомата Миля к Муру – аналогично как и в предыдущем переходе должны совпадать все алфавиты и все функции.
Для обеспечения совпадения функций выхода, надо вернуть или перевести выходной символ с ребра в вершину, в которую он входит, однако в случае если в вершину входят ребра с разными выходными символами, то данную вершину необходимо расщепить на такое количество, сколько разновидных входных символов имеется на всех входных ребрах.
В общем случае при переходе к автомату Мура число состояний может увеличиваться.
Если одно и тоже устройство описывается моделями автоматов Мура и Миля, то в модели на основе автомата Мура устройство может иметь больше число состояний.
Автомат Миля :
P1
/ W2
S1
S0
P1
/ W2
P1
/ W1
P2 / W1
S2
Автомат Мура :
S0/W1
S11/W2
P1
P1
/ W1
S111/W1
S2/W2
P1
P1
P1
P2