- •Конспект лекций
- •1. Теория множеств.
- •1.1. Множества
- •1.1.1. Свойства подмножеств.
- •1.1.2 Операции над множествами.
- •1.1.3 Алгебра теории множеств.
- •1.1.4 Решение уравнений алгебры множеств.
- •1.2. Кортеж.
- •1.2.2 График и свойства графика
- •1 .2.3. Свойства графиков.
- •1.3. Соответствия и отношения
- •1.3.1. Прямое (декартовое) произведение множество.
- •1.3.2. Соответствия.
- •1.2.1 Проекция множества.
- •1.3.2.1. Свойства соответствий.
- •1.3.3. Отношения.
- •1 .3.3.1. Операции над отношениями.
- •1.3.3.2 Основные свойства отношений.
- •1.4. Решетки.
- •1.4.1 Диаграммы Хассе.
- •1.4.2 Алгебраическое представление решеток.
- •2. Математическая логика
- •2.1. Высказывания
- •2.1.1. Высказывания и операции над высказываниями.
- •2.1.2. Операции над высказываниями.
- •2.2. Формулы математической логики.
- •2.2.1. Формулы равносильности.
- •2.3. Представление произвольной функции алгебры логики в виде формулы алгебры логики
- •2.4. Различные формы представления высказываний
- •2.5. Выполнимость формулы алгебры логики
- •Выполнимые.
- •2.6. Применение математической логики.
- •2.7. Минимизация сложных высказываний.
- •2.7.1. Метод Квайна.
- •2.7.2. Метод минимизирующих карт.
- •2.7.3. Метод минимизации с помощью карт Вейча.
- •2.8. Булевые функции и их свойства.
- •2.8.1. Функциональная полнота. Теорема Поста.
- •2.9. Логика предикат.
- •2.9.1. Логические операции над предикатами.
- •2.9.2. Квантовые операции.
- •2.9.3. Равносильные формулы логики предикатов.
- •2.9.4. Предваренная нормальная форма предиката
- •3. Теория графов
- •3.1. Основные понятия теории графов.
- •Перечислением:
- •Множеством образов:
- •Матрицей инцидентности
- •Матрицей смежности
- •3.2. Эйлеров граф.
- •3.3. Ядро графа.
- •3.3.1. Множество внутренней устойчивости графа
- •3.3.1.1. Алгоритм Магу для определения множества внутренней устойчивости графа
- •3.3.2. Множество внешней устойчивости графа
- •3.3.2.1. Алгоритм Магу для определения множества внешней устойчивости.
- •3.4. Множество путей в графе
- •3.5. Минимальный путь в графе.
- •3.5.1. Алгоритм фронта волны.
- •3.6. Ярусно-параллельная форма графов
- •3.6.1. Алгоритм приведения графа к ярусно-параллельной форме.
- •3.7. Деревья и леса
- •3.7.1. Алгоритм получения дерева из графа
- •4. Теория алгоритмов
- •4.1. Рекурсивная функция
- •4.2. Машина Тьюринга
- •4.2.1. Работа машины Тьюринга
- •4.3. Нормальные алгоритмы Маркова
- •4.3.1. Работа нормального алгоритма Маркова
- •5. Теория автоматов
- •5.1. Законы функционирования автоматов.
- •5.2. Задание автоматов
- •5.3. Минимизация автоматов
- •5.3.1. Алгоритм минимизации автомата Мили
- •5.3.2. Особенности минимизации автомата Мура.
- •5.3.3. Минимизация частичных автоматов.
- •5.4. Переход от автомата Мили к автомату Мура
- •5.5. Переход от автомата Мура к автомату Мили
- •6. Комбинаторика
- •6.1. Основные понятия.
- •6.2. Перестановки.
- •6.3. Размещения.
- •6.4. Сочетания.
- •6.5. Треугольник Паскаля.
- •6.6. Биномиальная формула (бином Ньютона).
- •7. Нечеткие множества
- •7.1. Введение
- •7.2. Основные определения.
- •7.3. Операции над нечеткими множествами.
- •7.3. Наглядное представление операций над нечеткими множествами.
- •7.4. Свойства основных операций над нечеткими множествами.
- •7.5. Алгебраические операции над нечеткими множествами.
- •8. Нечеткая логика.
- •8.1. Лингвистические переменные
- •8.2. Нечеткая истинность
- •8.3. Нечеткие логические операции
- •9. Литература
5. Теория автоматов
Автомат – дискретный преобразователь информации, который на основе входных сигналов, поступающих в дискретные моменты времени, и с учетом своего состояния вырабатывает выходные сигналы и изменяет свое состояние.
В данном разделе рассматриваются абстрактные автоматы, т.е. некоторая математическая модель. Вопросы практической реализации не рассматриваются. В связи с этим при построении автоматов будем иметь в виду, что:
Автомат функционирует в абстрактном времени.
Все переходы происходят мгновенно.
Автомат представляет собой кортеж 6 –го порядка:
, (5.1)
где – множество входных сигналов (входной алфавит),
– множество выходных сигналов (выходной алфавит),
– множество внутренних состояний,
– функция перехода,
– функция выхода,
- начальное состояние автомата.
5.1. Законы функционирования автоматов.
В зависимости от законов функционирования различают 3 вида автоматов:
Автоматы первого рода, или автоматы Мили:
(5.2)
Автоматы второго рода
(5.3)
Правильные автоматы второго рода, или автоматы Мура:
(5.4)
На практике наибольшее распространение получили автоматы Мили и автоматы Мура.
5.2. Задание автоматов
Автоматы могут быть заданы следующими способами:
В виде графа
РИС. 5.1. Автомат Мили
РИС. 5.2. Автомат Мура.
При
построении автомата Мили каждая дуга,
соединяющая вершины
и
,
имеет обозначение
.
Это означает следующее: находясь, в
состоянии
автомат, отрабатывая входной сигнал
,
выдает выходной сигнал
и переходит в состояние
.
Так как в автомате Мура выходной сигнал зависит только от текущего состояния , то каждая дуга, соединяющая вершины и , имеет обозначение .
В виде таблиц перехода и выхода (автомат Мили); отмеченной таблицы перехода (автомат Мура).
Автомат Мили описывается с помощью двух таблиц: таблицы перехода и таблицы выхода:
Таблица переходов (ТП) Таблица выходов (ТВ)
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Автомат Мура описывается с помощью отмеченной таблицы перехода:
Таблица переходов (ТП)
ПРИМЕР.
Синтезировать автомат, на вход которого подаются монеты номинальной стоимостью 1, 2 и 3 копейки, а на выходе автомат выдает билет, если сумма набранных монет составляет 3 копейки, если сумма меньше 3 копеек, то автомат ничего не выдает, если сумма больше 3 копеек, то автомат возвращает деньги.
Определим входной, выходной алфавиты и множество внутренних состояний:
входной алфавит
- монеты номинальной стоимостью 1, 2 и
3 копейки
выходной алфавит
- на выходе возможны выходные символы:
- ничего;
- билет;
- возврат.множество внутренних состояний
,
где - начальное состояние автомата « в автомате ничего нет»;
- «в автомате 1 копейка»;
- «в автомате 1 копейка»;
- «в автомате 2 копейки»;
-
«в автомате 3 копейки».
Г
раф
автомата имеет вид:
РИС. 5.3. Автомат Мили
Таблицы перехода и выхода представлены в виде:
Таблица переходов (ТП) Таблица выходов (ТВ)
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
1 |
Н |
Н |
Б |
Н |
2 |
|
|
|
|
|
2 |
Н |
Б |
В |
Н |
3 |
|
|
|
|
|
3 |
Б |
В |
В |
Б |
Неопределенным состоянием называется несуществующее состояние.
Частичным автоматом называется автомат, в котором некоторые состояния в таблице перехода не определены. Для дальнейшего исследования неопределенное состояние некоторым образом доопределяют.
