lec14
.pdf
Кафедра Прикладной математики Института информационных технологий РТУ МИРЭА
Дисциплина
«Математическая логика и теория алгоритмов»
2022-2023 уч.г.
Наполнение курса
Объем курса
16 лекционных и 8 практических занятий
Темы лекционных занятий
1.Элементы теории множеств. Булева алгебра
2.Булевы вектора и булевы функции
3.ДНФ, СДНФ, КНФ, СКНФ
4.Минимизация ДНФ
5.Метод Карно и метод Квайна
6.Двойственные функции
7.Функциональная полнота. Полные классы. Алгебра Жегалкина.
8.Замкнутые классы функций: монотонные, самодвойственные, сохраняющие const.
9.Теорема Поста
10.Исчисление высказываний
11.Исчисление предикатов. Основные положения. Кванторы
12.Нормальные формы. Доказательства
13.Конечные автоматы
14.Соединения и синтез автоматов
15.Машина Тьюринга
16.ЧРФ и НАМ
2
Лекция 14.
Соединения и синтез автоматов.
14.1Основные соединения автоматов.
14.2Триггеры.
14.3. Структурный синтез автоматов.
Часть 1.
Основные соединения автоматов.
1. Тривиальное параллельное соединение автоматов – это совокупность |
||||
двух автоматов с независимыми входами и выходами. |
X1 |
Y1 |
||
Если |
|
|
M1 |
|
M1 |
= {X1, Q1, Y1, φ1, ψ1} |
|
|
|
|
|
|
||
M2 |
= {X2, Q2, Y2, φ2, ψ2} |
|
X2 |
|
то у автомата М входной алфавит: X = X ×X , |
Y2 |
|||
|
1 |
2 |
|
M2 |
выходной алфавит: Y = Y1×Y2, |
|
|
||
множество состояний: Q = Q1×Q2. |
|
|
|
|
2. Параллельное соединение с одним алфавитом. |
|
Y1 |
||
У автомата М входной алфавит: X = X1 = X2, |
|
|||
|
M1 |
|||
выходной алфавит: Y = Y1×Y2, |
|
|
||
|
|
|
||
множество состояний: Q = Q1×Q2. |
|
X |
|
|
3. Последовательное соединение. |
|
|
Y2 |
|
У автомата М входной алфавит: X = X1, |
|
|
M2 |
|
выходной алфавит: Y = Y2, |
|
|
|
|
множество состояний: Q = Q1×Q2. |
|
|
|
|
|
X1 |
|
|
Y2 |
|
|
M1 |
M2 |
|
5
3. Соединения с обратной связью.
Имеется некоторый автомат М1 и автомат Мура М2. Некоторый вход автомата М1 является выходом автомата Мура М2 и наоборот.
У автомата М: |
X1 |
|
|
Y1 |
||
M1 |
||||||
|
|
|
|
|||
входной алфавит: X = X1×Y2, |
|
|
|
|
||
|
|
|
|
|
||
выходной алфавит: Y = Y1×X2, |
|
|
|
|
|
|
множество состояний: Q = Q1×Q2. |
Y2 |
|
|
X2 |
||
|
|
|
|
|
||
M2
!!! Возможны модификации, при которых происходит более мелкое разбиение алфавитов.
Синхронной сетью автоматов (ССА) называется схема,
использующая указанные соединения, причем в каждом контуре этой схемы должен быть хотя бы один автомат Мура. Он играет роль линии
задержки. В частности, СЛС является примером ССА. |
6 |
Часть 2.
Триггеры.
Автомат Мура называется полным (или совершенным), если возможны переходы из любого его состояния в любое другое с помощью подходящего входного символа, и разные состояния дают различные выходы.
Полный автомат Мура с двумя состояниями называется триггером.
D-триггер.
X |
|
Q |
|
|
0 |
|
1 |
0 |
0 |
|
0 |
1 |
1 |
|
1 |
ψ(q) |
0 |
|
1 |
Элемент задержки
(англ. delay).
T-триггер.
X |
|
Q |
|
0 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
ψ(q) |
0 |
1 |
Счетчик (англ. toggle – переключатель). Как бы подсчитывает количество импульсов, поступивших на его вход. 8
RS-триггер.
X |
|
Q |
|
R S |
0 |
|
1 |
0 0 |
0 |
|
1 |
0 1 |
1 |
|
1 |
1 0 |
0 |
|
0 |
1 1 |
- |
|
- |
ψ(q) |
0 |
|
1 |
(или SR)
(англ. set/reset).
Всостоянии 0 – запоминает вход S.
Всостоянии 1 –
запоминает инверсию входа R.
JK-триггер.
X |
|
Q |
J K |
0 |
1 |
0 0 |
0 |
1 |
0 1 |
0 |
0 |
1 0 |
1 |
1 |
1 1 |
1 |
0 |
ψ(q) |
0 |
1 |
Всостоянии 0 – запоминает вход J.
Всостоянии 1 –
запоминает инверсию входа K.
Так как разные состояния полного автомата Мура дают различные выходы, то можно считать, что между алфавитом состояний Q и выходным алфавитом Y имеются взаимно однозначные соответствия. Поэтому можно считать, что алфавит Q и Y совпадают. Отождествив соответствующие символы алфавитов, тогда ψ(q)=q, то есть функция выходов будет тождественной и в определении полного автомата Мура может не указываться.
9
Теорема о достаточном условии автоматной полноты.
Рассмотрим некоторую совокупность автоматов ∑.
Система ∑ называется автоматно-полной, если любой конечный автомат может быть реализован в виде ССА, в которой участвуют только автоматы из системы ∑ (ССА над cистемой ∑).
Теорема 14.1. Для того чтобы система автоматов была полной, достаточно чтобы она содержала хотя бы один полный автомат Мура и некоторую функционально-полную систему функциональных элементов. {M, f1…fS}
Доказательство:
Было доказано (утверждение 13.1), что любой автомат может быть представлен в виде СЛС, которая состоит из линии задержки и из некоторой функционально-полной системы функциональных элементов. Для доказательства теоремы достаточно доказать, что линии задержки можно представить в виде схемы над заданной системой.
10