Разработка компиляторов
Минимизация конечного автомата
Учитывая, что мы можем определять эквивалентные автоматы, хотелось бы научиться находить наименьший среди них. Задача нахождения наименьшего конечного автомата, распознающего данный язык, также разрешима, причем тоже конструктивным образом. Для описания процесса нахождения наименьшего конечного автомата, введем следующее определение.
Определение. Будем говорить, что строка различает состояния и , если существует такая входная цепочка , что является заключительным состоянием, а состояние не является заключительным состоянием, или, наоборот, не является заключительным состоянием, а состояние является заключительным состоянием.
Очевидно, что если некоторая строка различает состояния и такие, что и , то строка aw различает состояния и
Теперь перейдем к описанию процесса минимизации конечного автомата. Мы начнем с поиска и удаления всех недостижимых состояний. Затем мы должны найти такое разбиение множества состояний автомата, чтобы каждое подмножество содержало неразличимые состояния, т.е. если и принадлежат некоторому подмножеству, то для всех из и также принадлежат этому подмножеству.
Для этого мы разобьем множество состояний на два подмножества: и . В дальнейшем, мы попытаемся разбить каждое из подмножеств, соблюдая указанное выше условие. Если возникает ситуация, при которой мы не можем разбить никакое множество состояний, то мы заканчиваем процесс разбиения. В результате мы получим некоторый набор множеств состояний . Каждое из содержит только неразличимые состояния. Наконец, внесем в множество состояний минимизированного автомата по одному представителю каждого из множеств . На этом процесс завершается.
На следующем слайде мы приведем пример минимизации автомата.
