Основы кибернетики и вычислительной техники. Конечные автоматы Мили, Мура. Синтез конечного автомата

• Преподаватель приветствует студентов и проверяет, все ли его видят и слышат.  

• Предлагает поздороваться на русском языке, так как международные языки уже изучены.  

• Начинает лекцию с хорошего настроения и предлагает начать с повторения материала.  

• Преподаватель напоминает, что на прошлой лекции обсуждались автоматы, абстрактные, детерминированные и конечные автоматы.  

• Объясняет, что детерминированный конечный автомат можно представить как ручку с входными и выходными данными и состояниями.  

• Упоминает, что автомат можно представить в виде графа.  

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

• Описывает начальное состояние и функции перехода и выхода.  

• Упоминает, что алфавит состоит из двух символов: нуля и единицы.  

• Преподаватель объясняет, что детерминированные автоматы бывают двух видов: Мура и Мили.  

• Описывает, как работает автомат Мура и автомат Мили.  

• Подчеркивает, что автомат Мура проще в построении, но оба автомата можно преобразовать друг в друга.  

• Преподаватель объясняет, как построить автомат из алгоритма.  

• Описывает состояния автомата и переходы между ними.  

• Приводит пример простого алгоритма и строит граф, соответствующий автомату.  

• Проверка установки видеокарты.  

• Возможные недоработки в установке.  

• Построение графа автомата на основе алгоритма.  

• Переход из состояния Z1 в Z2 без условий.  

• Переход из Z2 в Z3 при условии X1 = 1 или X1 = 0.  

• Переход из Z3 в Z1 при X2 = 1 или Z4 при X2 = 0.  

• Переход из Z4 обратно в Z4 при X2 = 0 или в Z1 при X2 = 1.  

• Задание состояний с помощью двух битов памяти.  

• Четыре состояния: 00, 01, 10, 11.  

• Создание таблицы переходов для логического автомата.  

• Функции дельта и лямбда.  

• Таблица переходов как функция дельта.  

• Пример таблицы переходов для состояний Z1, Z2, Z3, Z4.  

• Переход из Z1 в Z2 при любых значениях X1 и X2.  

• Переход из Z2 в Z2 при X1 = 0 и X2 любое.  

• Переход из Z2 в Z2 при X1 = 0 и X2 любое.  

• Переход из Z2 в Z3 при X1 = 1.  

• Переход из Z3 в Z1 при X2 = 1 и Z4 при X2 = 0.  

• Переход из Z4 в Z4 при X2 = 0 и Z1 при X2 = 1.  

• Использование триггеров для сохранения состояний.  

• Применение T-триггеров для хранения состояний.  

• Изменение состояний триггеров при переходах.  

• Построение алгоритма действия устройства.  

• Построение графа переходов автомата.  

• Создание таблицы переходов для вычисления функций.  

• Рассматриваются функции дельта и лямбда.  

• Дельта зависит от декартового произведения зет и икс.  

• Лямбда зависит от зет и икс, давая на выходе игрек.  

• Пять функций: две функции перехода и три функции выхода.  

• Построение таблицы истинности для функций.  

• Использование логик фреймов для минимизации функций.  

• Построение логических схем для функций.  

• Описание автомата Мура: состояния, входные аргументы, функции перехода и выхода.  

• Построение конечного дискретного детерминированного автомата Мура.  

• Автомат Мили: выходная логика зависит от иксов.  

• Переход зависит от иксов и состояния.  

• Автомат Мили компактнее и функциональнее.  

• Построение алгоритма работы светофора.  

• Определение количества светофоров и кнопок.  

• Построение графа работы автомата и таблицы переходов.  

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

• Создание алгоритма работы устройства.  

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

• Взаимосвязь автоматов Мили и Мура.  

• Автомат Мили позволяет строить более сложные устройства.  

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

• Павел Алексеевич Некрасов и его доктрина свободной воли.  

• Независимость событий в законе больших чисел.  

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

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

• В одном автомате смесь черных и белых камушков 50/50, в другом черных больше.  

• Автомат переходит в состояние 0, если вытащили черный камушек, и в состояние 1, если вытащили белый.  

• В автомате возможны четыре перехода, вероятность зависит от предыдущего исхода.  

• Марков доказал, что отношение исходов стремится к равновесию.  

• Цепь Маркова позволяет предсказывать случайные события и оптимизировать сетевые процессы.  

• Автомат с магазинной памятью имеет дополнительную память, называемую стеком.  

• Стек работает по принципу очереди, загружая и выгружая данные в зависимости от состояния автомата.  

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

• Рассматриваются системы с бесконечным числом состояний.  

• Пример: железнодорожная линия с бесконечным числом станций.  

• Введение маркера, который может перемещаться по линии по определенным правилам.  

• Точки вдоль линии помечаются целыми числами.  

• Используется большая буква "н" для отслеживания маршрута системы.  

• Функция перехода маркера зависит от текущего такта времени.  

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

• Универсальная машина Тьюринга позволяет реализовать любой алгоритм.  

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

• Машина Тьюринга имеет одну ленту, а современные компьютеры - множество лент.  

• Компьютеры могут перемещаться по лентам произвольно, минуя промежуточные этапы.  

• Полнота по Тьюрингу означает, что любую вычислительную машину можно преобразовать в машину Тьюринга.  

• Машина Поста - аналог машины Тьюринга, разработанная Эмилем Постом.  

• Критерий выполнимости по Тьюрингу или Посту определяет, может ли алгоритм быть выполнен на вычислительном устройстве.  

• Эти критерии продвинули вычислительную технику и позволили программистам создавать универсальные алгоритмы.