Какой автомат называется нормализованным?

Всё множество совместимых состояний определяет некоторое множество минимизированных автоматов. Все они могут быть представлены нормализованным автоматом, в котором вместо состояний используются классы конечной совместимости. Для получения нормализованного автомата в процессе минимизации нужно строго следить за тем, чтобы начальное состояние всегда находилось в классе с индексом 1.

При построении нормализованного автомата переход δ = (Сi, zj)считается неопределённым, если для всех состояний этого класса не определены переходы в другое состояние.

Если хотя бы для одного состояния класса переход определён, то в клетку таблицы нормализованного автомата заносится индекс класса, в который переходит цифровой автомат из этого состояния.

Таким образом, доопределяются неопределённые переходы исходного автомата.

Нормализованный автомат является эквивалентным любому из минимизированных автоматов и не имеет, как минимум, ни одной пары совместимых состояний. В соответствии с изложенной методикой минимизации получаются либо полностью определённые, либо частичные нормализованные автоматы. У полностью определённых автоматов классы конечной совместимости не пересекаются, поэтому нормализованный автомат является единственным и процесс минимизации этим заканчивается. В случае получения частичного автомата классы i– совместимости пересекаются. Это приводит к тому, что нормализованный автомат может описываться конечным количеством вариантов таблиц или графов. В случае частичных автоматов часто отказываются от достижения абсолютной минимизации и ограничиваются нахождением нормализованного автомата и его эвристическим доопределением.

Дата добавления: 2015-07-26; просмотров: 201; Нарушение авторских прав

Мы поможем в написании ваших работ!