(мал. 2). Для полегшення читаності графа не показано стан помилки і переходи з усіх станів недетермінірованного автомата в стан помилки по залишилися вхідним символам. br/>
Граф переходів недетермінірованного автомата S
В
Рис. 2
5. ЗВЕДЕННЯ недетермінірованного кінцевих автоматів до детермінованого
Для кожного недетермінірованного кінцевого распознавателя існує еквівалентний детермінований автомат, який допускає ті ж ланцюжка, що і недетермінірованний.
Позначення:
АН - недетермінірованний автомат;
АТ - еквівалентний йому, детермінований автомат.
Процедура побудови АТ за АН:
. Помітити перший рядок таблиці переходів для АД безліччю початкових станів автомата АН. p align="justify">. За даним множині станів B, позначаю рядок таблиці
переходів автомата АТ, для якої переходи ще не виконані, обчислити ті стани АН, які можуть бути досягнуті з B за допомогою кожного вхідного символу і помістити отримане безліч станів у стан комірки для автомата АТ. . Для кожного нового безлічі, породженого на кроці 2, подивитися: чи мається вже в АД рядок, позначений цим безліччю, якщо ні, то створити новий рядок і позначити її цим безліччю. Якщо безліч вже використовувалося як мітка, то ніяких дій не треба.
. Якщо в таблиці АТ є рядок, для якої ще не обчислені переходи, то повернутися назад і застосувати до цього рядка крок 2. Якщо всі переходи обчислені, то переходимо до кроку 5. p align="justify">. Помітити рядок як допускає стан АТ, тоді і тільки тоді, коли вона містить допускає стан АН, інакше позначити як відхилено. p align="justify"> Додамо стан помилки R і у всіх порожніх клітинах запишемо перехід в стан помилки. Отримаємо детермінований автомат таблицею переходів якого є таблиця 4. p align="justify"> Таблиця 4 Таблиця переходів детермінованого автомата
Побудуємо граф переходів детермінованого автомата (мал. 3). Для полегшення читаності графа не показано стан помилки і переходи з усіх станів детермінованого автомата в стан помилки по залишилися вхідним символам. p align="center"> детермінований автомат праволінейний граматика
Граф переходів детермінованого автомата
В
Рис. 3
6. ПОБУДОВА МІНІМАЛЬНОГО АВТОМАТА
Для отримання мінімального автомата скористаємося методом розбиття. Метод розбиття полягає в розбитті безлічі станів на непересічні підмножини (блоки), такі, що нееквівалентні стану потрапляють в різні блоки. p align="justify"> Умови еквівалентності станів:
умова подібності: стану S і T повинні бути або обидва допускають, або обидва отвергающими;
...
