Алексеев В. Б. - Дискретная математика - Автоматы

• Автомат - это система, которая преобразует входные последовательности из алфавита А в выходные последовательности из алфавита Б.  

• Автомат задается шестью объектами: алфавит А, алфавит Б, функция перехода, функция выхода, начальное состояние и канонические уравнения автомата.  

• Рассмотрим автомат, который преобразует входную последовательность из алфавита А в выходную последовательность из алфавита Б.  

• Для этого автомата определены канонические уравнения, которые определяют отображение из А-бесконечность в Б-бесконечность.  

• Автомат может преобразовывать конечные слова, но не ограничен по длине входных слов.  

• В видео обсуждается понятие автомата и его представление в виде диаграммы Мура.  

• Автомат - это устройство, которое преобразует входную последовательность символов в выходную последовательность символов.  

• Представление автомата в виде диаграммы Мура - это ориентированный граф с множеством вершин и дугами, которые показывают, как автомат переходит из одного состояния в другое.  

• В видео вводится понятие схемы из функциональных элементов, которые реализуют преобразования последовательности символов.  

• Схема - это представление автомата в виде набора функциональных элементов, которые преобразуют входную последовательность в выходную.  

• Вводится определение истока в ориентированном графе и ациклического графа.  

• Утверждается, что в любом ациклическом графе есть хотя бы один исток.  

• Вводится понятие схемы из функциональных элементов, которая представляет собой ориентированный ациклический граф, где каждому истоку приписана переменная, а каждая вершина имеет функцию из базиса, зависящую от количества входящих дуг.  

• Входы схемы могут быть как истоками, так и выходами.  

• Глубина вершины определяется как максимальное число дуг в пути из истоков в данную вершину.  

• Функционирование схемы определяется индукцией по глубине вершин, где для каждой вершины определяется функция, реализуемая в этой вершине.  

• Если глубина вершины равна нулю, то это исток, и в этой вершине реализуется функция тождественно равная входной переменной.  

• Если глубина вершины больше нуля, то в этой вершине реализуется функция, зависящая от входных переменных и приписанных функций из базиса.  

• Определяются функции, которые реализуются в вершинах схемы.  

• Схема реализует набор функций, которые могут быть реализованы в выходных вершинах.  

• Схема реализует конъюнкцию и сумму по модулю два.  

• Схема называется "сигма штрих".  

• С помощью схемы функциональных элементов можно реализовать любую функцию алгебры логики.  

• Схема может быть древесной.  

• В базисе добавляются элемент задержка и ориентированные циклы.  

• Функционирование схемы определяется дискретным временем и обработкой входных данных.  

• В схеме происходит задержка приходящего символа на один такт времени и его отправка дальше по схеме.  

• В каждый момент времени на каждом выходе образуется либо ноль, либо единица.  

• Две теоремы: первая утверждает, что определенные схемы и задержки реализуют автоматное отображение, вторая утверждает, что для каждого автомата существует схема, его моделирующая.  

• На упражнениях студенты должны доказать эти теоремы в обе стороны.