Кроки для перетворення NFA на DFA:
- Крок 1: Спочатку Q' = ϕ
- Крок 2: Додайте q0 NFA до Q'. …
- Крок 3: Знайдіть у Q' можливий набір станів для кожного вхідного символу. …
- Крок 4. У DFA кінцевим станом будуть усі стани, які містять F (кінцеві стани NFA)
Для кожного NFA можна знайти детермінований скінченний автомат (DFA), який приймає ту саму мову. тому можна перетворити існуючий NFA на DFA з метою впровадження (можливо) простішої машини.
Побудова підмножини — це алгоритм, який використовується для перетворення недетермінованого кінцевого автомата (NFA) в еквівалентний детермінований кінцевий автомат (DFA) шляхом створення моделі, яка фіксує всі дійсні конфігурації NFA у відповідь на вхідні рядки.
Щоб знайти замикання ε, держава сама у своїй закритості. Потужність замикання ε: | ε закриття (стан) | або кількість елементів у наборі ε замикання. ε закриття стану 'S' = { S, T, A, E }, оскільки S є початковим станом, а T, A, E доступні за допомогою ε .
Крок 1: побудуйте відповідний Таблиця переходів NFA. Зрештою, ця таблиця допоможе перетворити DFA з відповідного NFA. {A, B}(На діаграмі NFA можна побачити, що A переходить як до A, так і до B) Крок 2: Використовуйте цю таблицю та почніть рухатися по всіх станах і спробуйте створити таблицю DFA.
Крок 1: Створіть діаграму переходів для заданого регулярного виразу, використовуючи NFA з переміщеннями ε. Крок 2: потім перетворіть цей NFA з ε на NFA без ε. Крок 3: Нарешті, перетворіть отриманий NFA в еквівалентний DFA.