Эквивалентное разбиение множеств автоматов

Эквивалентное разбиение автомата, состоящего из множества автоматов Ḿ={M₁, М₂,..., M_N}, представляет собой разбиение Ḿ на классы таким образом, что два автомата принадлежат одному и тому же классу тогда и только тогда, когда они являются эквивалентными. Каждый класс автоматов в этом разбиении называется классом эквивалентных автоматов. Очевидно, что автоматы не могут быть эквивалентными, если они несравнимы. Следовательно, до разбиения на классы эквивалентных автоматов множество Эй следует сначала разбить на подмножества таким образом, чтобы два автомата относились к одному и тому же подмножеству тогда и только тогда, когда они сравнимы. Впоследствии каждое подмножество может индивидуально подвергаться дальнейшему разбиению. Поскольку разбиение множества автоматов в соответствии с их входным алфавитом является тривиальной задачей, то потеря общности будет незначительной, если мы предположим, что все автоматы в Ḿ сравнимы. При таком допущении можно построить расщепляемый автомат ∆(M₁, М₂,..., M_N) так, как было описано в § 2.7. Разбиение автомата ∆(M₁, М₂,..., M_N) на обычные классы эквивалентности любым из описанных в §§ 3.6—3.8 способов, выявляет, являются ли любые два автомата M _i и М _j, из множества Ḿ эквивалентными. Действительно, по определению 3.3, М _i и M _j являются эквивалентными, если каждый класс эквивалентности, который содержит состояние автомата M _i, также содержит состояние автомата M _j и если каждый класс эквивалентности, который содержит состояние автомата M _j содержит также состояние автомата М _i, в противном случае М _i и M _j являются различимыми. Когда определены все пары эквивалентных автоматов из множества Ḿ, эквивалентное разбиение автоматов из Ḿ может быть произведено с помощью алгоритма, аналогичного алгоритму 3.1 (в котором теперь рассматриваются не состояния, а автоматы).

В случаях, когда число автоматов N велико, определение классов эквивалентности автоматов облегчается построением так называемой таблицы эквивалентности для расщепляемого автомата ∆(M₁, М₂,..., M_N). Эта таблица имеет строку для каждого класса эквивалентности автомата ∆(M₁, М₂,..., M_N) и столбец для каждого автомата M _i из множества Ḿ. Общий вид таблицы эквивалентности показан в таблице 3.11. Клетки таблицы эквивалентности заполняются в соответствии со следующим правилом: в клетке, где пересекаются строка {σh₁, σh₂,..., σhr_h} и столбец М _i, ставится 1, если какое-нибудь состоян ie в классе эквивалентности {σh₁, σh₂,..., σhr_h} принадлежит автомату M _i, и 0 — в противном случае. Таким образом, M _i и M _j являются эквивалентными тогда и только тогда, когда столбцы M _i и M _j являются одинаковыми во всех строках таблицы эквивалентности. Поэтому эквивалентное разбиение автоматов приводит к разбиению столбцов таблицы эквивалентности на подмножества таким образом, что два столбца принадлежат одному и тому же подмножеству в том и только в том случае, если они одинаковы во всех строках. Разбиение столбцов может быть выполнено вручную даже для большого числа N, при этом сразу получается эквивалентное разбиение автоматов без составления перечня всех пар эквивалентных автоматов.

Для иллюстрации, на рис. 3.8 приведены автоматы A11, A12, A13 и A14, объединенные в один расщепляемый автомат ∆(A11, A12, A13 и A14).

Таблица переходов для этого расщепляемого автомата представлена в таблице 3.12. Применение любого из методов эквивалентного разбиения, описанных в §§ 3.6—3.8, показывает,

что для ∆(A11, A12, A13, A14) классами эквивалентности являются {1, 4, 5, 7, 9, 12}, {2, 3, 6, 10, 11} и {8}.

Таблица 3.13 представляет собой таблицу эквивалентности для ∆(A11, A12, A13, A14), которая показывает, что

эквивалентным разбиением автоматов для множества автоматов {A11, A12, A13, A14} является {A11, A12, A14} и {A13}.

Заметим, что в процессе эквивалентного разбиения автоматов мы получаем также обычное эквивалентное разбиение каждого автомата из заданного множества. Например, эквивалентное разбиение ∆(A11, A12, A13, A14), как видно из таблицы 3.13, показывает, что эквивалентное разбиение A11 есть {1, 4} и {2, 3}, эквивалентное разбиение A12 — {5, 7} и {6}, эквивалентное разбиение A13—{8}, {9} и {10} и эквивалентное разбиение A14 — {11} и {12}.