1. DFA: DFA відноситься до детермінованого кінцевого автомата. Скінченний автомат (FA) називається детермінованим, якщо у відповідності до вхідного символу існує єдиний результуючий стан, тобто є лише один перехід. Детермінований скінченний автомат складається з п’яти кортежів, представлених у вигляді:
Де,
Q: Непорожній кінцевий набір станів у кінцевому управлінні (qo, q1, q2, …).
Σ: непорожній кінцевий набір вхідних символів.
δ: це функція переходу, яка приймає два аргументи, стан і вхідний символ, вона повертає один стан.
qo: це початковий стан, один із станів у Q.
F: Це непорожній набір кінцевих станів/станів, що приймають із набору, що належить Q.
2. ПРИЧИНИ:
NFA відноситься до недетермінованого кінцевого автомата. Скінченний автомат (FA) називається недетермінованим, якщо існує більше ніж один можливий перехід з одного стану на той самий вхідний символ.
Недетермінований скінченний автомат також є набором із п’яти кортежів і представлений у вигляді,
Де,
Q: Набір непорожніх кінцевих станів.
Σ: набір непорожніх кінцевих вхідних символів.
δ: це функція переходу, яка приймає стан із Q та вхідний символ із і повертає підмножину Q.
qo: Початковий стан NFA та член Q.
F: непорожній набір кінцевих станів і член Q.
Передумова – Готово Автоматично
Різниця між DFA і NFA:
| DFA | NFA |
|---|---|
| DFA означає Deterministic Finite Automata. | NFA означає Nondeterministic Finite Automata. |
| Для кожного символічного представлення алфавіту існує лише один перехід стану в DFA. | Не потрібно вказувати, як NFA реагує на певний символ. |
| DFA не може використовувати перехід порожній рядок. | NFA може використовувати перехід порожній рядок. |
| DFA можна розуміти як одну машину. | NFA можна розуміти як кілька маленьких машин, що обчислюють одночасно. |
| У DFA чітко встановлюється наступний можливий стан. | У NFA кожна пара стану та вхідного символу може мати багато можливих наступних станів. |
| DFA складніше побудувати. | NFA легше побудувати. |
| DFA відхиляє рядок, якщо він завершується в стані, який відрізняється від стану прийняття. | NFA відхиляє рядок, якщо всі гілки вмирають або відхиляють рядок. |
| Час, необхідний для виконання вхідного рядка, менше. | Час, необхідний для виконання вхідного рядка, більше. |
| Усі DFA є NFA. | Не всі NFA є DFA. |
| DFA вимагає більше місця. | NFA вимагає менше місця, ніж DFA. |
| Мертва конфігурація не допускається. наприклад: якщо ми надаємо вхідні дані як 0 у стані q0, ми повинні вказати 1 як вхідні дані для q0 як самоциклу. | Допускається мертва конфігурація. наприклад: якщо ми надаємо вхід як 0 у стані q0, ми можемо ввести наступний вхід 1 у q1, який перейде до наступного стану. |
| δ: QxΣ -> Q, тобто наступний можливий стан належить Q. | δ: Qx(Σ U ε) -> 2^Q, тобто наступний можливий стан належить набору потужностей Q. |
| Зворотне відстеження дозволено в DFA. | Зворотне відстеження не завжди можливо в NFA. |
| Перетворення регулярного виразу на DFA складно. | Перетворення регулярного виразу на NFA простіше порівняно з DFA. |
| Епсилонне переміщення заборонено в DFA | Епсилонний рух дозволено в NFA |
| DFA дозволяє лише один хід для одного введення алфавіту. | Може бути вибір (більш ніж один хід) для одного введення алфавіту. |