5 Построение минимального автомата

Минимальный автомат — это автомат, имеющий наименьшее возможное количество состояний и реализующий заданную функцию выходов. Алгоритм построения минимального автомата предложен Ауфенкампом и Хоном: Находить последовательные разбиения автомата на классы эквивалентных между собой состояний, до тех пор, пока на каком-то шаге не окажется, что разбиение даёт все классы эквивалентности состояний автомата. Всем состояниям, принадлежащим классу эквивалентности, приписать общее обозначение. Получить минимальный автомат путём «объединения» одинаково обозначенных состояний в одно состояние. Способы объединения зависят от того, каким образом определён автомат — таблицей, графом или матрицей. Некоторые способы получения минимальной формы в зависимости от вида определения автомата: Таблица переходов. Если заданы таблица переходов и эквивалентное разбиение автомата, то таблица переходов минимального автомата может быть построена следующим образом: заменить обозначение каждого состояния в таблице на обозначение класса, которому оно принадлежит, и из каждой группы строк с одинаковыми обозначениями в клетках основного столбца вычеркнуть все строки, кроме одной. Граф переходов. Если заданы граф переходов (диаграмма состояний) и эквивалентное разбиение автомата, то граф переходов минимального автомата может быть построен так: заменить обозначение каждого состояния в графе на обозначение класса, к которому относится данное состояние, объединить все одинаково обозначенные состояния и представить объединённые состояния одним состоянием, имеющим общее обозначение. Из каждой группы дуг, имеющих общее исходное и общее конечное состояние, вычеркнуть все, кроме одной. Матрица переходов. Если заданы матрица переходов и эквивалентное разбиение автомата, то матрица переходов минимального автомата может быть построена так: провести симметрическую перестановку и симметрическое разбиение так, чтобы строки (и столбцы) группировались соответственно классам эквивалентности, заменить все обозначения строк (и столбцов) каждой группы, представляющей класс эквивалентности, одним обозначением этого класса, заменить каждую подматрицу в разбитой матрице одной клеткой, содержащей все пары вход-выход, которые имеются в любой строке этой подматрицы. Также для построения минимального автомата можно использовать алгоритм Бржозовского, основанный на методе производных Бржозовского, который предполагает посимвольное сокращение исходного регулярного выражения до тех пор, пока не будет получено тривиальное выражение. 01:31 Технический долг и эквивалентность состояний 03:25 Доказательство факта о классах эквивалентности 10:38 Оценка сложности алгоритма 14:20 Заключение и дальнейшие задачи 15:42 Доказательство автоматности языка 17:29 Теорема Махила-Нероуда 19:02 Пример неавтоматного языка 21:00 Переход к более высокому уровню 22:35 Определение порождающей грамматики 26:05 Пример грамматики 31:49 Отношение выводимости 33:59 Пример распознавания слов 35:33 Пример разбора слова 36:46 Виды грамматик 40:20 Автоматы и грамматики 44:07 Соответствие грамматик и машин 46:21 Доказательство теоремы 54:44 Вывод слов из автомата 55:35 Переход в пустое слово 57:11 Переход в обратную сторону 58:35 Доказательство перехода 01:01:09 Построение грамматики по автомату 01:03:36 Построение грамматики по автомату 01:07:40 Индукция по числу шагов 01:10:00 Завершение доказательства