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

Июль 31, 2022

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

Содержание

2. 1. Основні означення і поняття
3. Приклад 1 (неформальна мінімізація) Стани F,G недосяжні. Стани B,C еквівалентні. Стани D,E еквівалентні. Класи еквівалентності: {A},
4. 2. Алгоритм вилучення недосяжних станів скінченного автомата а) Занесемо в список L початковий стан і відмітимо
5. Детермінізація НСА з можливою появою недосяжних станів НСА ДСА Всі стани досяжні!!! Етапи мінімізації: Вилучення недосяжних
6. 3. Мінімізація скінченного автомата за допомогою побудови класів еквівалентності
8. Приклад 2. Мінімізації скінченного автомата методом побудови класів еквівалентності (метод 1.1) L: A,F,D,E,B,C Символ а не
9. Символ а не розрізнив стани класу еквівалентності К2, символ b – розрізнив. К2 розділяється на два
10. b
11. Метод побудови класів еквівалентності (метод 1.2 - інший спосіб запису)
12. Класи еквівалентності не змінилися!!! Мінімізований автомат
13. 4. Функція переходів і розширена (узагальнена) функція переходів недетермінованого скінченного автомата
14. Приклад 3 (для НСА) Автомат, який дозволяє ланцюжки, що закінчуються на 01 Розглянемо ланцюжок 00101. Альтернативи:
15. Рекурсивний алгоритм побудови розширеної функції переходів
16. Приклад обчислення розширеної функції переходів для ДСА
17. Приклад 3 (продовження) Розглянемо ланцюжок 00101. Побудова функції переходів за алгоритмом: НСА
18. 5. Мінімізація скінченного автомата за допомогою таблиці нееквівалентних станів
19. Схема алгоритму:
20. Приклад 5. Мінімізації скінченного автомата за допомогою таблиці нееквівалентних станів (метод 2) А В С Е
22. Скачать презентацию

Слайд 2

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

Слайд 3

Приклад 1 (неформальна мінімізація)
Стани F,G недосяжні. Стани B,C еквівалентні. Стани D,E

еквівалентні. Класи еквівалентності: {A}, {B,C}, {D,E} p, q, r

Слайд 4

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

початковий стан і відмітимо його в Q.
б) Якщо список L порожній, то - кінець алгоритму. Якщо ні, то ми вилучаємо із L перший елемент (позначаємо його B) і робимо пункт в).
в) Поміщаємо в кінець списку L такі невідмічені стани C з Q, для яких є ребро, що веде з B в C і відмічаємо ці вершини в Q. Виконуємо пункт б).

Q: νA ν B ν C ν D ν E ...F ...G

L:ABCDE

Слайд 5

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

НСА
ДСА
Всі стани досяжні!!!
Етапи мінімізації:
Вилучення недосяжних

станів
Об'єднання еквівалентних станів

Слайд 6

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

Слайд 7

Слайд 8

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

A,F,D,E,B,C

Символ а не розрізнив стани класу еквівалентності K1, символ b – також.

Слайд 9

Символ а не розрізнив стани класу еквівалентності К2, символ b –

розрізнив. К2 розділяється на два класи: K3={B,C}, K4={D,E}

Слайд 10

b

Слайд 11

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

Слайд 12

Класи еквівалентності
не змінилися!!!
Мінімізований автомат

Слайд 13

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

Слайд 14

Приклад 3 (для НСА)
Автомат, який дозволяє ланцюжки, що закінчуються на

01

Розглянемо ланцюжок 00101. Альтернативи:

Слайд 15

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

Слайд 16

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

Слайд 17

Приклад 3 (продовження)
Розглянемо ланцюжок 00101. Побудова функції переходів за алгоритмом:
НСА

Слайд 18

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

Слайд 19

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

Слайд 20

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

2)

А В С Е F G

С,G –нееквівалентні
A,H-нееквівалентні
A,G-нееквівалентні

D- недосяжний стан
Еквівалентні стани:

Етапи мінімізації:
Вилучення недосяжних станів
Об'єднання еквівалентних станів

0