Проаналізувати Ізоморфізм і еквівалентність автоматів.

Нехай S = (As, Qs, Vs, ds, ls) і T = (Ат, QT, VT, dт, lт) - Два автомата. Трійка відображень f:

Аs -> Ат, g: Qs -> Qт, h: Vs -> Vт називається гомоморфізмом автомата S в автомат Т, якщо для будь-яких a Î As, q Î Qs, v Î Vs виконані умови:

dт (g (q), f (a)) = g (ds (q, a)) (2.4 а)

lт (g (q), f (a)) = h (ls (q, a)) (2.4 б)

Автомат Т називається гомоморфним автомату S. Якщо всі три відображення сюр'ектівни, то ця трійка називається гомоморфізмом S на Т. Якщо, крім того, ці три відображення взаємно однозначні, то вони називаються изоморфизмом S на T; автомати, для яких існує ізоморфізм, називаються ізоморфними. Ясно, що потужності відповідних алфавітів ізоморфних автоматів повинні бути однаковими.

Поняття ізоморфізму має для автоматів той же зміст, що і для алгебр, що розглядалися раніше: автомати S і Т ізоморфні, якщо входи, виходи і стану S можна перейменувати так, що таблиця переходів автомата S перетвориться в таблицю переходів автомата Т. Ізоморфізм графів переходів (без урахування букв, написаних на ребрах) є необхідною, але недостатньою умовою ізоморфізму відповідних автоматів.

Приклад 2.4. а. Візьмемо як S автономний автомат із прикладу 2.3, а. В якості Т-автономний автомат, граф якого наведено на рис. 2.3. Існує гомоморфізм S в Т. Відповідна трійка відображень така: f тривіально, оскільки обидва вхідних алфавіту складаються з однієї літери, g і h задамо списками (тут і в аналогічних випадках замість qi-> rj, будемо писати i -> j), g = {1-> 4, 2-> 3, 3> 3, 4> 2, 5> 1, 6> 2, 7> 1, 8-> 6, 9> 7}, h = {0-> v, 1-> w, 2-> w}. Ніяке стан S не відобразилося в r3; зауважимо, що r5 недосяжно з інших стані. Це - загальне правило: якщо стан Т не входить в область значень g при гомоморфізм, то воно має бути недосяжним для будь-якого стану з цієї області, інакше порушиться умова (2.4). Якщо з автомата Т стан r5 разом з інцидентним йому ребром видалити, то отримаємо новий автомат Т '; описана трійка відображень є гомоморфізмом S в Т і S на Т '. Як показує цей приклад, число станів і вихідних букв при Гомоморфизмом може не зберігатися. Для неавтономних автоматів це ж відноситься і до вхідного алфавітом.

б. У графі автомата Т рис. 2.3 поміняємо місцями літери на двох ребрах: на ребрі (r1, r2) напишемо v, а на ребрі (r2, r1) напишемо w. Отримаємо автомат Т ", граф якого ізоморфний графу Т; проте сам автомат Т» не ізоморфний Т. Дійсно, при ізоморфізмі графів вершина r4 автомата Т ізоморфна вершині r4. автомата Т "; проте Т (r4, aaa) = vvv, Т" (r4, aaa) = vvw, і при будь-якому перейменування виходів у вихідному слові Т (r4, aaa) всі три букви будуть однаковими, а в T "(r4, ааа) - ні.

Перехід від автомата.S до еквівалентного автомату називається еквівалентним перетворенням автомата S. Можна ставити різні завдання про пошук автоматів, еквівалентних даному і володіють заданими властивостями. Найбільш вивченою серед таких завдань є завдання про мінімізацію числа станів автомата, або, коротше, про мінімізацію автомата: серед автоматів, еквівалентних S, знайти автомат з найменшим числом станів - мінімальний автомат.