Алгоритми мінімізації скінченних автоматів

Завдання мінімізації автомата зводиться до пошуку його мінімальної форми (мінімального автомата). Мінімальний автомат — це автомат, що має найменшу можливу кількість станів і реалізує задану функцію виходів.

Принцип побудови

Мінімальна форма автомата S (позначається як Š) у теорії автоматів являє собою автомат з ň станами, що утворюють множину 1..σň}. Мінімальний автомат з S будується так. Характеристичні функції автоматів S та Š позначаються gs, gz і g's , g'z відповідно. Тоді, якщо
, то
.

Таким чином, при побудові Š за заданою умовою не виникає ніякої невизначеності.

Алгоритм знаходження мінімального автомата запропонували Ауфенкамп і Хон. Вони показали, що для знаходження мінімального автомата необхідно знаходити послідовні розбиття Pi автомата S на класи 1, 2, …, k, (k+1) — еквівалентних між собою станів, аж поки на якомусь (k+1) кроці не виявиться, що Pk = Pk+1. Таким чином, розбиття Pk дає всі класи еквівалентності станів автомата S. Всім станам S, що належать до класу еквівалентності Σl можна приписати загальне позначення, наприклад, σl. Таким чином, автомат Š виходить з автомата S «​​об'єднанням» однаково позначених станів у один стан. Способи, якими це об'єднання проводиться, істотно залежать від того, яким способом визначено автомат — таблицею, графом чи матрицею.

Способи отримання мінімальної форми

Таблиця переходів

Якщо задано таблицю переходів і еквівалентне розбиття Σ1..Σň автомата S, то таблицю переходів Š можна побудувати так:

  1. Замінити позначення кожного стану, наявного в таблиці S, позначенням класу, якому цей стан належить.
  2. З кожної групи рядків з однаковими позначеннями в клітинах основного стовпця викреслити всі рядки, крім одного.

Отримана при цьому таблиця є таблицею переходів Š.

Граф переходів

Якщо задано граф переходів (діаграму станів) і еквівалентне розбиття Σ1..Σň автомата S, то граф переходів Š можна побудувати так:

  1. Замінити позначення кожного стану, наявного в графі переходів S, позначенням класу, до якого належить цей стан.
  2. Об'єднати всі однаково позначені стани (розглядаючи дуги графу як «гнучкі зв'язки») і подати об'єднані стани одним станом, який має спільне позначення.
  3. З кожної групи дуг, що мають спільний початковий і спільний кінцевий стан викреслити всі, крім однієї.

Отриманий у результаті граф буде графом Š.

Матриця переходів

Якщо задано матрицю переходів і еквівалентне розбиття Σ1..Σň автомата S, то матрицю переходів Š можна побудувати так:

  1. Провести симетричну перестановку і симетричне розбиття [S] так, щоб рядки (і стовпці) групувалися за класами еквівалентності S (цю ж матрицю можна отримати при матричному методі еквівалентного розбиття).
  2. Замінити всі позначення рядків (і стовпців) кожної групи, що представляє клас еквівалентності, одним позначенням цього класу.
  3. Замінити кожну підматрицю в розбитій матриці однією клітинкою, що містить усі пари вхід-вихід, які є в будь-якому рядку цієї підматриці (усі рядки в будь-якій такій підматриці містять одну і ту ж множину пар вхід-вихід).

Отримана в результаті матриця є матрицею переходів Š.

Властивості мінімальної форми

Якщо Š є мінімальною формою автомата S, то:

  1. Š є єдиною мінімальної формою з точністю до позначення станів
  2. Š = S
  3. Ніякі два стани Š не є еквівалентними
  4. Не існує автомата, еквівалентного S і меншого (з меншим числом станів), ніж Š.

Див. також

Посилання

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.