Эквивалентность и минимизация автоматов-распознавателей

Очевидно, что два распознавателя следует считать эквивалентными, если они распознают один и тот же язык. Проблема эквивалентности двух распознавателей A и B состоит в нахождении ответа на вопрос: совпадают ли языки, распознаваемые A и B. Проблема минимизации распознавателя A состоит в нахождении такого распознавателя A', который, распознавая тот же язык, что и A, имеет минимально возможное число состояний. Оказывается, что проблемы эквивалентности и минимизации конечных автоматов-распознавателей только в некоторых чертах отличаются от таковых для конечных автоматов-преобразователей.

Определение 15. Пусть A=SA, X, s0A, δ A, FA и B=SB, X, s0B, δ B, FB – два конечных автомата-распознавателя с одним и тем же входным алфавитом. Их прямым произведением называется автомат
A× B=SA× SB, X, (s0A, s0B), δ A× B, FA× FB, где

∀ sA∈ SA, ∀ sB∈ SB, ∀ x∈ X δ A× B ((sA, sB), x)=(δ A (sA, x), δ B (sB, x)).

Как и для автоматов-преобразователей, прямое произведение автоматов-распознавателей – это просто два автомата с одними и теми же входами, работающие синхронно.

Теорема 5. (Теорема Мура) Два конечных автомата-распознавателя с одинаковым входным алфавитом являются эквивалентными тогда и только тогда, когда при их синхронном функционировании под воздействием одних и тех же входных символов они на каждом шаге всегда попадают либо оба в заключительные, либо оба в незаключительные состояния.

Определение 16. Два состояния p и q конечного автомата-распознавателя A=S, X, s0, δ, F называются эквивалентными, если для любой цепочки α ∈ X* функции δ *(p, α) и δ *(q, α) попадают либо оба в заключительные, либо оба в незаключительные состояния.

Для автомата, изображённого на рис. 7, состояния s3 и s5 эквивалентны. Любая входная цепочка, поданная на автомат, находящийся в состоянии s3, будет недопустима, точно так же, как и в случае, когда автомат находится в состоянии s5. Эквивалентные состояния можно объединить в один класс и построить новый автомат, состояниями которого являются классы эквивалентных состояний. Если мы можем определить на множестве состояний автомата максимально возможное разбиение на классы эквивалентности, то, выбирая его классы эквивалентности как новые состояния, получим минимальный автомат, эквивалентный исходному автомату.

Алгоритм минимизации конечного автомата-распознавателя состоит в построении на множестве его состояний таких разбиений π 0, π 1, …, что в один класс разбиения π k попадают k -эквивалентные состояния, то есть находящиеся в отношении эквивалентности ≈ k. При подаче на вход пустой цепочки автомат остается в том же состоянии, в котором он находился. Поэтому разбиение π 0 состоит из двух блоков: в один блок попадают все заключительные состояния, а в другой – все незаключительные состояния. Определив, как строить следующее разбиение из предыдущего, мы сможем последовательно построить всю цепочку π 0, π 1, …

Теорема 6. Пусть в конечном автомате-распознавателе p≈ kq, k≥ 0. Для того чтобы p≈ k+1q, необходимо и достаточно, чтобы ∀ x∈ X δ p, x≈ kδ q, x.

Теорема 7. Пусть выполняется минимизация конечного автомата-распознавателя и π k+1=π k. Тогда для любого i> k π i=π k.

Рассмотрим пример минимизации конечного автомата, заданного таблицей переходов. Начальное состояние здесь 0, заключительные состояния – 1, 3, 7.

Начальное разбиение представляет собой два блока, включающие один заключительные, а другой – незаключительные состояния. Поэтому

π 0={A0=0, 2, 4, 5, 6, 8, 9, B0=1, 3, 7}.

Разбиение π 1 в один блок объединяет те состояния, которые нельзя различить при подаче цепочек длиной 1, то есть те, которые под воздействием одного и того же входного сигнала переходят в один и тот же блок разбиения π 0.

π 1={A1=0, 5, 8, B1=2, 4, 6, 9, C1=1, D1=3, 7}.

Следующее разбиение π 2 в один блок объединяет те состояния, которые под воздействием одного и того же входного сигнала переходят в один и тот же блок предыдущего разбиения π 1.

π 2={A2=0, 5, 8, B2=2, 4, 6, 9, C2=1, D2=3, 7}.

Разбиение π 2 совпадает с разбиением π 1. Таким образом, минимальный автомат с эквивалентным поведением имеет 4 состояния, представляющих блоки разбиения π 2. Начальным состоянием здесь является состояние 0, 5, 8, заключительными – два состояния 1 и 3, 7.