детермінірованного автомата до детермінованого:
Позначення:
АТ - детермінований автомат
АН - недетермінірованний автомат
. Помітити перший рядок таблиці переходів для АД безліччю початкових станів автомата АН. p align="justify">. За даним множині станів B, позначаю рядок таблиці переходів автомата АТ, для якої переходи ще не виконані, обчислити ті стани АН, які можуть бути досягнуті з B за допомогою кожного вхідного символу і помістити отримане безліч станів у стан комірки для автомата АТ.
. Для кожного нового безлічі, породженого на кроці 2, подивитися: чи мається вже в АД рядок, позначений цим безліччю, якщо ні, то створити новий рядок і позначити її цим безліччю. Якщо безліч вже використовувалося як мітка, то ніяких дій не треба. p align="justify">. Якщо в таблиці АТ є рядок, для якої ще не обчислені переходи, то повернутися назад і застосувати до цього рядка крок 2. Якщо всі переходи обчислені, то переходимо до кроку 5. p align="justify">. Помітити рядок як допускає стан АТ, тоді і тільки тоді, коли вона містить допускає стан АН, інакше позначити як відхилено. p align="justify">. Додамо стан помилки Er і у всіх порожніх клітинах запишемо перехід в стан помилки. p align="justify"> Отримаємо наступний детермінований автомат (див. табл. 4).
Таблиця 4. Детермінований автомат
x 0 x 1 x 2 x 4 x 5 x 6 x 7 {S} {Er} {Er} {C} {Er } {S 1 F} {Er} {C} 0 {F} {Er} {F < span align = "justify"> 4 } {Er} {Er} {F 1 } {F 7 } {F 1 } 0 {C} {Er} {Er} {Z} {E} {Er} {E} {Er} 0 {S 1 S 3 } {Er} {S 2 } {S 4 } {Er} {Er} {Er} {Er} 0 {F 7 } {Er} {Er} {Er} {Er} {Er} {Er} {F 8 } 0 {F 4 } {Er} {F 5 } {Er...
