- •Раздел 1. Алгебраические структуры Тема 1.1. Бинарные операции и их свойства
- •Тема 1.2. Алгебраические структуры
- •Тема 1.3. Основные свойства групп
- •Тема 1.4. Поля и кольца
- •Раздел 2. Алгебра множеств Тема 2.1. Основные определения теории множеств
- •Тема 2.2. Подмножество, понятие универсального множества
- •Тема 2.3. Операции над множествами
- •Раздел 3. Основные теоремы комбинаторики
- •Тема 3.1. Метод математической индукции
- •Тема 3.2. Основные принципы комбинаторики
- •Раздел 4. Комбинаторные объекты Тема 4.1. Сочетания
- •Тема 4.2. Размещения и перестановки
- •Раздел 5. Полиномиальные тождества Тема 5.1. Бином Ньютона
- •Тема 5.2. Понятие о методе рекуррентных соотношений
- •Тема 5.3. Метод производящих функций
- •Тема 5.4. Метод траекторий
- •Тема 5.5. Примеры комбинаторных задач
- •Раздел 6. Соответствие, отношение, отображение Тема 6.1. Понятие кортежа. Декартово произведение множеств
- •Тема 6.2. Определения и свойства
- •Тема 6.3. Типы отношений
- •Пересечение и объединение отношений
- •Композиция отображений и отношений
- •Тема 6.5. Решётки
- •Тема 6.4. Верхняя и нижняя границы множества.
- •Раздел 7. Операции булевой алгебры Тема 7.1.Понятие высказывания, простые и составные высказывания
- •Тема 7.2.Операции на множестве высказываний
- •Отрицание
- •Конъюнкция
- •Дизъюнкция
- •«Исключающее или»
- •Импликация
- •Эквивалентность
- •Штрих Шеффера
- •Раздел 8. Законы и тождества Булевой алгебры Тема 8.1.Формулы Булевой алгебры
- •Тема 8.2.Законы и тождества Булевой алгебры
- •Тема 8.3.Составление формулы по заданной таблице истинности
- •Тема 8.4. Двойственность
- •Тема 8.5.Булева алгебра и теория множеств
- •Тема 8.6.Днф, интервалы и покрытия
- •Раздел 9. Функциональная полнота. Алгебра Жегалкина
- •Тема 9.1.Функционально полные системы
- •Тема 9.2.Алгебра Жегалкина и линейные функции
- •Тема 9.3.Замкнутые классы. Монотонные функции
- •Тема 9.4.Теоремы о функциональной полноте
- •Раздел 10. Хорновские формулы
- •Тема 10.1.Задача получения продукции
- •Тема 10.2.Решение задачи о продукции
- •Алгоритм замыкание(X,f)
- •Алгоритм ПрямаяВолна(X,y,f)
- •Алгоритм БыстроеЗамыкание(X,f)
- •Раздел 11. Теория релейно-контактных схем Тема 11.1.Основные понятия
- •Тема 11.2.Основные задачи теории релейно-контактных схем
- •Тема 11.3.Построение машины голосования
- •Тема 11.4.Двоичный сумматор
- •Тема 11.5.Методы упрощения логических выражений. Методы решения логических задач
- •Раздел 12. Логика предикатов Тема 12.1.Определение предиката
- •Тема 12.2.Логические операции над предикатами
- •Тема 12.3.Кванторы
- •Тема 12.4. Истинные формулы и эквивалентные соотношения
- •Тема 12.5.Доказательства в логике предикатов
- •Раздел 13. Теория графов
- •Тема 13.1.Основные определения теории графов
- •Тема 13.2. Способы задания графов
- •Тема 13.3. Отношения порядка и эквивалентности на графе
- •Тема 13.4. Числовые характеристики графа
- •Тема 13.5.Изоморфизм графов
- •Раздел 14. Проблемы достижимости на графах Тема 14.1.Граф достижимости
- •Тема 14.2.Взаимная достижимость, компоненты сильной связности и базы графа
- •Раздел 15. Некоторые классы графов Тема 15.1.Деревья
- •Тема 15.2. Обход графа
- •Тема 15.3. Расстояния. Диаметр, радиус и центр графа. Протяжённости.
- •Раздел 16. Машина Тьюринга
- •Тема 16.1. Формальное описание машины Тьюринга
- •Тема 16.2. Примеры построения машины Тьюринга
- •Тема 16.3. Свойства машины Тьюринга как алгоритма
- •Раздел 17. Машина Поста
- •Тема 17.1. Теоретическая часть. Состав машины Поста
- •Тема 17.2. Применимость программ. Определение результата выполнения программ
- •Раздел 18. Основные понятия теории автоматов Тема 18.1. Общие подходы к описанию устройств, предназначенных для обработки дискретной информации
- •Тема 18.2. Способы задания конечного автомата
- •Тема 18.3. Эквивалентные автоматы
- •Тема 18.4. Автоматы Мура и Мили
- •Тема 18.5. Примеры синтеза автоматов
Тема 18.2. Способы задания конечного автомата
Комбинационные схемы, хотя и позволяют реализовать любые фиксированные зависимости между входными и выходными сигналами, не могут изменять характера своего поведения (т.е. последовательности обработки данных) – любое такое изменение требует изменения структуры схемы, т.е., по сути, переходу к другой схеме. Решить проблему перестройки работы без изменения структуры схемы возможно, если ввести в неё элементы памяти, которые позволяли бы фиксировать и сохранять промежуточные состояния устройства – в этом случае выходной сигнал будет зависеть не только от входного сигнала, но и от состояния схемы. Если количество таких элементов конечно, то, как указывалось выше, дискретное устройство будет называться конечным автоматом.
Как указывалось ранее,задаёт порядок преобразования входных символов и состояния автомата на предыдущем такте в состояние на последующем, а– преобразования входных символов и состояния автомата на текущем такте в выходной символ. Если– начальное состояние автомата, а– номер такта, то его работа описывается системой:
Данные соотношения получили название системы канонических уравнений конечного автомата. Пользуясь ими можно, начиная с, последовательно находить все последующие состояния автомата и выходные символы.
Выделяются два типа автоматов – инициальные и неинициальные. В инициальных автоматах начальное состояние фиксировано (т.е. они всегда начинают работать из одного и того же состояния ). В неинициальных автоматах в качестве начального состояния может быть выбрано любое из множества; этим выбором определяется дальнейшее поведение автомата.
Представление конкретного конечного автомата фактически сводится к описанию задающих его автоматных функций. При конечном числе возможных внутренних состояний количество возможных значений автоматных функции также оказывается конечным. Их описание возможно различными способами, наиболее распространёнными из которых является табличный и с помощью диаграмм.
В табличном способе автоматные функции задаются двумя конечными таблицами, именуемыми соответственно матрицей переходов и матрицей выходов. В этих таблицах строки обозначаются буквами входного алфавита, а столбцы – буквами внутреннего алфавита (символами, кодирующими внутреннее состояние автомата). В матрице переходов на пересечении строки () и столбца () помещаются значения функции, а в матрице выходов – значения функции.
Пример
По заданному табличному представлению автомата построить систему его команд. Пусть конечный автомат имеет алфавиты ={a, b}= {a, b, c},= {1, 2, 3}, а автоматные функции задаются таблицами:
| ||||||||
1 |
2 |
3 |
1 |
2 |
3 | |||
a |
3 |
3 |
1 |
a |
b |
a |
b | |
b |
2 |
3 |
3 |
b |
c |
c |
c |
Представленные две таблицы можно объединить в одну, условившись в каждую клетку на первую позицию ставить значение , а через запятую на вторую позицию помещать значение. В результате получится следующая «сводная» таблица:
,
| |||
1 |
2 |
3 | |
a |
3,b |
3,a |
1,b |
b |
2,c |
3,c |
3,c |
Видно, что таблица стала весьма напоминать таблицу, задающую функциональную схему машины Тьюринга. Из неё легко просматриваются команды преобразования, осуществляемые данным автоматом:
Пусть на начальном такте автомат находится в состоянии = 1 и на его вход в последующие такты подаётся последовательность abb. Пользуясь перечнем команд можно установить, что автомат преобразует эту последовательность в bcc и при этом окажется в состоянии 3.
Другой вариант описания автоматных функций – графический. Он обладает большей наглядностью, чем табличный. Состояния автомата задаётся посредством ориентированного графа, который называется диаграммой (точнее, диаграммой Мура). Вершины графа помечены символами из алфавита состояний автомата, а каждой командесоответствует ребро, идущее из вершиныв вершину; при этом ребру приписывается метка. Таким образом, ребро возникает в том случае, если автомат, находящийся в состоянии, посредством некоторого входного сигналаможет быть переведён в состояние. Если такой перевод возможен при нескольких входных воздействиях,…,, и при этом формируются выходные сигналы,…,, то ребру приписывается выражение.
Для диаграмм, представляющих конечный автомат, справедливы следующие утверждения:
из одной вершины не может выходить двух рёбер с одинаковым входным символом (условие однозначности);
если при работе автомата реализуется входная комбинация , то обязательно существует ребро, идущее из вершиныпомеченное символом(условие полноты);
количество вершин и ребер диаграммы является конечным.
Пример
Построить диаграмму для конечного автомата, описанного в предыдущем примере.
Если на начальном такте автомат находился в состоянии = 1 и на его вход в последующие такты подавались символы abb, то, пользуясь диаграммой, можно проследить последовательность преобразований:– выходные символы будут появляться в порядке bcc.