Мінімізація скінченного автомата. (Тема 5) презентация

Тема 5: Мінімізація скінченного автомата 1. Основні означення і поняття 2. Алгоритм вилучення недосяжних станів скінченного автомата 3. Мінімізація скінченного автомата за допомогою побудови класів еквівалентності 4. Функція переходів і розширена (узагальнена) функція переходів недетермінованого скінченного автомата 5. Мінімізація скінченного автомата за допомогою таблиці нееквівалентних станів

1. Основні означення і поняття

Приклад 1 (неформальна мінімізація)

2. Алгоритм вилучення недосяжних станів скінченного автомата

Детермінізація НСА з можливою появою недосяжних станів

3. Мінімізація скінченного автомата за допомогою побудови класів еквівалентності

Приклад 2. Мінімізації скінченного автомата методом побудови класів еквівалентності (метод 1.1)

Метод побудови класів еквівалентності (метод 1.2 - інший спосіб запису)

4. Функція переходів і розширена (узагальнена) функція переходів недетермінованого скінченного автомата

Приклад 3 (для НСА)

Рекурсивний алгоритм побудови розширеної функції переходів

Приклад обчислення розширеної функції переходів для ДСА

Приклад 3 (продовження)

5. Мінімізація скінченного автомата за допомогою таблиці нееквівалентних станів

Схема алгоритму:

Приклад 5. Мінімізації скінченного автомата за допомогою таблиці нееквівалентних станів (метод 2)

Приклад 5. (продовження)