- •Теория автоматов. Уровни представления эвм.
- •Операционные элементы. (оэ)
- •Процессор гса:
- •Достоинства и недостатки.
- •Операционное устройство для выполнения операций алгебраического сложения двоичных чисел.
- •Суммирование при использовании прямого кодирования.
- •Суммирование чисел при использовании обратного кода.
- •Дополнительный код.
- •Модифицированный код.
- •Пример суммирования.
- •Конечные автоматы.
- •Теория конечных автоматов
- •Способы задания функций переходов.
- •Автоматы ( с выходным преобразователем)
- •Способы задания автоматов
- •Способы задания автомата Миля
- •Преобразование автоматов из Миля в Мура и обратно Понятие эквивалентности автоматов
- •Преобразование Мура в Миля
- •Техника преобразований.
- •Обратный переход. Построение Мура для заданного Миля.
- •Частичные или не полностью определенные автоматы.
- •Синтез конечных автоматов.
- •Абстрактный синтез конечных автоматов.
- •Построение дерева входных последовательностей.
- •Структурный этап синтеза автоматов.
- •Основные этапы структурного синтеза.
- •Типы памяти.
- •Основные типы триггеров.
- •Пример структурного синтеза синхронного автомата.
- •`Временная диаграмма.
- •Этап минимизации автомата при абстрактном синтезе. Минимизация полностью определенного автомата.
- •Алгоритмы минимизации на основе треугольной матрицы.
- •Минимизация числа состояний частичного автомата.
- •Минимизация частичного автомата.
- •Абстрактный этап синтеза конечного автомат. (неканонический метод).
- •Алгоритм перехода от граф схемы микропрограммы к автомату Мура.
- •Учет взаимодействия проекционного и управляющего автоматов. Алгоритм получения.
- •Алгоритм получения частичного автомата.
- •Множество входных значений.
- •Кодирование состояний синхронного автомата.
- •Кодирование соседними кодами.
- •Минимизация числа переключений элементов памяти.
- •Универсальный способ кодирования (для синхронного автомата).
- •Автомат с дешифратором.
- •Асинхронные автоматы.
- •Этапы синтеза асинхронного автомата.
- •Реализация асинхронного rs триггера на логических элементах.
- •Установочные входы в триггерах.
- •Синхронные элементы памяти.
- •Требования, предъявляемые к синхросигналу.
- •Синтез синхронного rs триггера.
- •Синтез триггера с задержкой.Реализация асинхронного t триггера.
- •Исключение состязаний элементов памяти в синхронных автоматах.
- •Структура автоматов на плм и пзу.
- •Явление рисков в комбинационных узлах.
- •Исключение влияние рисков.
- •Построение схем без риска.
- •Алгоритм построения схемы без рисков по днф.
- •Алгоритм построения схемы без риска.
- •Автоматы, языки и грамматики.
- •Задача распознавания цепочек языка.
- •Классификация грамматик по Хомскому.
- •Примеры построения грамматик.
- •Грамматика для выполнения арифметических операций.
- •Соответствие конечных автоматов и автоматных грамматик.
- •Этапы для заданной автоматной грамматики.
- •Этапы для заданной автоматной грамматики.
- •Недетерминированные конечные автоматы.
- •Преобразование недетерминированного автомата в детерминированный.
- •Преобразование некоторых типов грамматики к автоматному ввиду.
- •Алгоритм получения правил, не содержащих правил вывода нетерминальных символов.
- •Построение распознавателей и преобразователей.
- •Построение распознавателей.
- •Алгоритм построения преобразователя.
Грамматика для выполнения арифметических операций.
Пример грамматики, определяющей множество правил построения арифметических выражений, использующих правила сложения и умножения.
Vт ={I , X , + , ( , )}
Vn ={ E }
E
R = {Ei+E;EI;Ei*E;E{E}}
E=>i+E=>i+E=>i+(E)=>i+(i*E)=>i+(i*i)
Набор данных правил не обеспечивает скобки для первых операндов.
Vт ={I , X , + , ( , )}
Vn ={ E }
E
R= {EE+E;EE*E;E(E);Ei}
E=>E+E=>E+E*E=>i+i*I (1244)
E=>E*E=>E*i=>E+E*i=>i+i*i(24144)
Для одной и той же цепочки получили два синтаксического разбора, следовательно грамматика не однозначна.
Грамматика не обеспечивает приоритет операций сложение и умножение. Чтобы обеспечить приоритеты операций мы можем операции суммирования сделать в скобках, тогда:
R = (E9E+E);EE*E,Ei)
E => (E+E) => (E+(E*E)) => (i+(i*i))
E => (E*E) => ((E+E)*E) => ((i+i)*i)
Грамматика получилась неоднозначной, однако каждая операция оказалась в своей скобке.
Приоритетность операции умножить по отношению к операции сложить обеспечивается благодаря скобкам.
Vт = {I, * , + , ( , )}
Vn={E,T,P}
E– арифметическое выражение
Т – слагаемое (или терм)
Р – произведение или сам множитель
R={ET,EPPP*P,P(T)*P,PP*(T)*P,PP*P,PI,TT+P,TP+T,TP+T,TT+T,Ti}
Нужно получить : i + i * i
8,8 i+P*P
5 i+P
12 T+P
9 T
3 E
E=>T=>T + P => либоT+(T)*P=>T+(T)*I либо i+P=>i+(I)*P=>i+(T+T)*P либо i+(T+T)*i=>i+(i+i)*I либо T+(T+T)*i=>i+(i+i)*i
Данная грамматика полностью удовлетворяет требованиям арифметической операции для умножения и суммирования, однако она не однозначна. Если в правилах в правой части существует два разных нетерминальных символа, то грамматика будет неоднозначна.
Соответствие конечных автоматов и автоматных грамматик.
Цепочка символов входного алфавита автомата называется допустимой, если в результате действий этой цепочки автомат из начального состояния переходит в конечное.
Множество допустимых цепочек автомата называется языком, который допустим данным автоматом.
Утверждение:
Для каждой автоматной грамматики может быть построен конечный автомат допускающий язык, который порождается заданной грамматикой.
Этапы для заданной автоматной грамматики.
Этап
Преобразование автоматной грамматики.
Ac
AcZ (AZc) Z – конец
К грамамтики добавляется нетерминальный символ Z, который называется конечным.
Правила вида Ac, гдеA- нетерминальный символ, аc– терминал, заменяют на правилаAcZилиAZcв зависимости от того левосторонняя или правосторонняя грамматика.
Вводят дополнительное правило ZE, гдеEпустой символ, который относят кнетерминальным.
Этап
Построение графа автомата и разметка.
Ставим в соответствие каждому нетерминальному символу вершину графа, который помечается этим символом.
Для каждого правила AcB,AB– нетерминал,c– терминальный символ ставится в соответствие дуга между вершинамиAиB, которые помечаются символомc
Этапы для заданной автоматной грамматики.
Начальному символу грамматики сопоставляется начальное состояние автомата
Алфавиту нетерминальных символов – алфавит состояний.
Алфавиту терминальных символов – алфавит входных слов.
Операции Zeсоответствует конечная вершина автомата.
Правилам грамматики соответствует функции перехода автомата.
Пример построения:
Vт = {с,d}
Vn={I}
I
R= {Ic;IIc;IId}
T=>Ic=>Id=>Iddc=>cddc
Цепочка росла справа налево , так как грамматика левосторонняя.
Построим автомат:
Vn={I, Z}
R = {IZc , IIc , IId , Ze }
S = {I , Z}
Z- конечная вершина
Автомат является недетерминальным так как из Iпод воздействием с у нас два перехода. ИзIZ;IIподаем ранее получаемую цепочку на вход автомата, начиная с крайне правила символа.
|
c |
d |
d |
c |
I |
I |
I |
I |
Z |
Автомат оказался в конечном состоянии значит цепочка является допустимой. Пусть задан автомат в виде формировании предыстории, без выходного преобразователя.
A=<P , S , s0 , φ>
Vт :Pставим в соответствие алфавиту терминальных символов входного алфавита
Vn:Sалфавит нетерминальных символов – алфавит состояний.
I: s0
Получаем правила из функции возбуждения.
Следовательно si sj
Vт = {0,1}
Vn={I,A,B}
I
R = {I0I;I1I;A0A;A1B;B0B;B1}
В результате преобразования видно, что имеется между автоматными грамматиками и автоматами существует взаимнооднозначное соответствие, следовательно грамматику можно рассматривать как форму представления конечного автомата.