Алгоритм Бжозовского и Маккласки

Алгоритм Бжозовского и Маккласки

Алгоритм Бжозовского и Маккласки интенсивно использует графическое представление автомата. Сам автомат обобщается, допуская в качестве меток перехода не только буквы, но и обычные выражения. Начиная с автомат закончив, мы постепенно исключаем состояния, и в конце концов мы получаем автомат с одним переходом. Метка этого перехода является регулярным выражением для языка, распознаваемого автоматом.

Обобщенный автомат определяется как традиционный недетерминированный конечный автомат со следующими особенностями:

• он имеет одно начальное состояние α и одно конечное состояние ω
• переходы помечаются регулярными выражениями
• ни один переход не входит в α и ни один переход не выходит из конечного состояния ω.

Можно легко превратить обычный автомат В в обобщенный автомат: достаточно добавить состояния α и ω и ε-переходы из α в начальные состояния В, и ε-переходы терминальных состояний В в сторону ω.

Сокращение автомата

Учитывая обобщенный автомат, мы вычисляем обобщенный автомат с меньшим количеством переходов или состояний, применяя приведенные ниже преобразования без изменения распознанного языка. В конце остаются только два состояния α и ω и переход α и ω, метка которого является регулярным выражением, обозначающим распознаваемый язык. Преобразования — это редукции переходов и редукции состояний.

Для редукции состояния должны быть выполнены все пути, проходящие через это состояние (в соседнее состояние). Затем язык, распознаваемый этим путем, добавляется к сокращенному автомату (см. пример).

В следующем примере показаны основные возможные сокращения, а также регулярные выражения, сгенерированные на автомате:

Что дает следующий обобщенный автомат:

Мы исключаем q2: путь q0 -> q2 -> q3 дает язык a², поэтому он добавляется к пути q0 -> q3. Путь q3 -> q2 -> q3 дает язык ba или (ba)*, потому что это цикл на q3 -> q3.

Исключаем q1: здесь петля по q1 даст a*

Исключаем q0:

Исключаем q3:

Обратите внимание, что полученное выражение также зависит от порядка исключения, но все сгенерированные языки равны.