1 Err0F1ErrErr
F2 ErrErrErrErrErr0F2ErrErrErrErr
F3 ErrErrErr0F3ErrErrErrErrErrErr
F4 Err0F4ErrErrErrErrErrErrErrErr1F5ErrErr
F6 ErrErrErrErrErr0F6ErrErrErrErr
F7 ErrErrErr0F7ErrErrErrErrErrErr
F8 Err0F8ErrErrErrErrErrErrErrErr1F9
F10 ErrErrErrErrErrErrErr0F10ErrErrErrErrErrErrErrErr0F11ErrErrErrErrErrErr
F11 Err1ErrErrErrErrErrErrErrErrErr0
Побудуємо граф переходів недетермінірованного автомата (мал. 2). Для полегшення читаності графа не показано стан помилки і переходи з усіх станів недетермінірованного автомата в стан помилки по залишилися вхідним символам. br/>
Граф переходів недетермінірованного автомата
S
В
Рис. 2
5. Зведення недетермінірованного кінцевого автомата до детермінованому
Для кожного недетермінірованного кінцевого распознавателя існує еквівалентний детермінований автомат, який допускає ті ж ланцюжка, що і недетермінірованний.
Позначення:
АН - недетермінірованний автомат;
АТ - еквівалентний йому, детермінований автомат.
Процедура побудови АТ за АН:
. Помітити перший рядок таблиці переходів для АД безліччю початкових станів автомата АН. p align="justify">. За даним множині станів B, позначаю рядок таблиці
переходів автомата АТ, для якої переходи ще не виконані, обчислити ті стани АН, які можуть бути досягнуті з B за допомогою кожного вхідного символу і помістити отримане безліч станів у стан комірки для автомата АТ. . Для кожного нового безлічі, породженого на кроці 2, подивитися: чи мається вже в АД рядок, позначений цим безліччю, якщо ні, то створити новий рядок і позначити її цим безліччю. Якщо безліч вже використовувалося як мітка, то ніяких дій не треба.
. Якщо в таблиці АТ є рядок, для якої ще не обчислені переходи, то повернутися назад і застосувати до цього рядка крок 2. Якщо всі переходи обчислені, то переходимо до кроку 5. p align="justify">. Помітити рядок як допускає стан АТ, тоді і тільки тоді, коли вона містить допускає стан АН, інакше позначити як відхилено. p align="justify"> Додамо стан помилки R і у всіх порожніх клітинах запишемо перехід в стан помилки.
Отримаємо детермінований автоматтабліцей переходів якого...
