1 Конечные автоматы
Конечный автомат — математическая модель вычислений. Она представляет собой абстрактную машину, которая может находиться в одном из нескольких состояний. Переход между состояниями происходит в соответствии с входными сигналами. Существует два основных типа конечных автоматов: Детерминированный (ДКА). Для каждого состояния и каждого входного символа существует только один возможный переход в следующее состояние. Недетерминированный конечный автомат (НКА). Возможны несколько возможных переходов в следующее состояние. Конечные автоматы широко используются в информатике, электронике, других областях для моделирования и реализации разных систем. Например: распознавание символов (действительных чисел, ключевых слов в языке программирования или электронных адресов); анализ и обработка текста (для выделения синтаксиса, проверки орфографии, поиска и замены текста в текстовых редакторах); управление процессами (для моделирования и управления сложными процессами в системах управления двигателем, сети, роботах); проектирование цифровых схем в электронике (например, для реализации счётчиков, таймеров, регистров); разработка алгоритмов для поиска в строках, сжатия данных, шифрования. 00:05 Введение в курс 00:51 Теоретическая и практическая составляющие курса 02:27 Темы курса 03:52 Экзамен и система оценивания 06:26 Практическая и теоретическая части 12:09 Литература и структура курса 14:40 Введение в алфавит и слова 16:06 Конкатенация языков 17:24 Определение слова 19:39 Мощность множества слов 21:22 Введение в недетерминированный конечный автомат 25:27 Пример недетерминированного конечного автомата 29:40 Понятие достижимости и конфигурации 31:09 Переход из конфигурации в конфигурацию 32:37 Определение достижимости по автомату 38:25 Определение языка, распознаваемого автоматом 40:03 Вопросы и ответы по достижимости 42:57 Нетерминированность и распознавание слов 45:23 Метрики и ошибки в автоматах 47:50 Повторение определения достижимости 49:15 Пример с автоматом 50:08 Индукция по количеству шагов 52:31 Переход и индукция 55:27 Упрощение конструкции автомата 58:25 Доказательство утверждения 01:02:13 Утверждение о переходах 01:06:44 Доказательство корректности переходов 01:08:47 Формальное доказательство 01:12:15 Доказательство корректности 01:17:10 Завершение доказательства 01:23:23 Заключение и упражнения
Конечный автомат — математическая модель вычислений. Она представляет собой абстрактную машину, которая может находиться в одном из нескольких состояний. Переход между состояниями происходит в соответствии с входными сигналами. Существует два основных типа конечных автоматов: Детерминированный (ДКА). Для каждого состояния и каждого входного символа существует только один возможный переход в следующее состояние. Недетерминированный конечный автомат (НКА). Возможны несколько возможных переходов в следующее состояние. Конечные автоматы широко используются в информатике, электронике, других областях для моделирования и реализации разных систем. Например: распознавание символов (действительных чисел, ключевых слов в языке программирования или электронных адресов); анализ и обработка текста (для выделения синтаксиса, проверки орфографии, поиска и замены текста в текстовых редакторах); управление процессами (для моделирования и управления сложными процессами в системах управления двигателем, сети, роботах); проектирование цифровых схем в электронике (например, для реализации счётчиков, таймеров, регистров); разработка алгоритмов для поиска в строках, сжатия данных, шифрования. 00:05 Введение в курс 00:51 Теоретическая и практическая составляющие курса 02:27 Темы курса 03:52 Экзамен и система оценивания 06:26 Практическая и теоретическая части 12:09 Литература и структура курса 14:40 Введение в алфавит и слова 16:06 Конкатенация языков 17:24 Определение слова 19:39 Мощность множества слов 21:22 Введение в недетерминированный конечный автомат 25:27 Пример недетерминированного конечного автомата 29:40 Понятие достижимости и конфигурации 31:09 Переход из конфигурации в конфигурацию 32:37 Определение достижимости по автомату 38:25 Определение языка, распознаваемого автоматом 40:03 Вопросы и ответы по достижимости 42:57 Нетерминированность и распознавание слов 45:23 Метрики и ошибки в автоматах 47:50 Повторение определения достижимости 49:15 Пример с автоматом 50:08 Индукция по количеству шагов 52:31 Переход и индукция 55:27 Упрощение конструкции автомата 58:25 Доказательство утверждения 01:02:13 Утверждение о переходах 01:06:44 Доказательство корректности переходов 01:08:47 Формальное доказательство 01:12:15 Доказательство корректности 01:17:10 Завершение доказательства 01:23:23 Заключение и упражнения