2 Свойства конечных автоматов Регулярные языки

Некоторые свойства конечных автоматов и регулярных языков: Конечный автомат — это ориентированный конечный граф, дуги которого взвешены символами алфавита. В начале обработки строки автомат находится в начальном состоянии. Далее он просматривает символы один за другим, осуществляя переходы между состояниями в соответствии с весами, размещёнными на дугах. Если в определённый момент из состояния нет исходящей дуги, соответствующей текущему символу входной строки, автомат отклоняет строку. Если строка завершилась, а автомат не достиг терминального состояния, строка также отклоняется. Если по завершению входной строки автомат оказался в терминальном состоянии — строка считается принятой и принадлежащей языку, который описывается этим автоматом. Регулярные языки замкнуты относительно различных операций. Например, объединения, пересечения, дополнения, обращения, конкатенации. Описания языков в виде конечных автоматов эквивалентны описаниям в виде регулярных выражений. 00:05 Введение и обзор курса 00:41 Определение и свойства конечных автоматов 02:11 Алгоритм распознавания слова 05:22 Построение множества кукаты 11:19 Проверка принадлежности слова языку 13:25 Хранение и обработка переходов 17:28 Заключение и оценка алгоритма 18:51 Мощность слова и переходы 21:03 Асимптотика и память 22:24 Детерминированный конечный автомат 25:48 Построение детерминированного автомата 30:25 Пример построения автомата 32:17 Доказательство леммы 37:02 Доказательство индукции 38:52 Обозначение множеств 45:04 Доказательство принадлежности слова языку 50:04 Применение автоматов в компиляторах 53:06 Построение полного детерминированного конечного автомата 58:05 Замкнутость автоматных языков 01:00:13 Примеры доказательств 01:04:17 Дополнение и регулярные выражения 01:10:53 Регулярные автоматы 01:15:01 Индукция по длине слова 01:18:02 Фиксация состояний и переходы 01:18:55 Добавление переходов 01:19:22 Стартовое и завершающее состояния 01:19:49 Заключение