TechCodeview

• NFA означає недетерміновані кінцеві автомати. Для даної звичайної мови легко побудувати NFA, ніж DFA.
• Скінченні автомати називаються NFA, якщо існує багато шляхів для певного введення від поточного стану до наступного стану.
• Кожен NFA не є DFA, але кожен NFA може бути перекладений на DFA.
• NFA визначається так само, як і DFA, але за наступними двома винятками, він містить кілька наступних станів і містить перехід ε.

На наступному зображенні ми можемо бачити, що від стану q0 для входу a є два наступних стани q1 і q2, аналогічно, від q0 для входу b наступні стани q0 і q1. Таким чином, не фіксовано чи визначено, куди йти далі з певним введенням. Тому цю ФА називають недетермінованими скінченними автоматами.

Формальне визначення NFA:

NFA також має п’ять станів, як і DFA, але з іншою функцією переходу, як показано нижче:

 &#x3B4;: Q x &#x2211; &#x2192;2<sup>Q</sup> 

де,

 Q: finite set of states ∑: finite set of the input symbol q0: initial state F: final state δ: Transition function 

Графічне представлення NFA

NFA можна представити орграфами, які називаються діаграмами стану. В якому:

1. Стан представлено вершинами.
2. Дуга, помічена символом введення, показує переходи.
3. Початковий стан позначено стрілкою.
4. Кінцевий стан позначено подвійним колом.

приклад 1:

 Q = {q0, q1, q2} ∑ = {0, 1} q0 = {q0} F = {q2} 

рішення:

Діаграма переходу:

Таблиця переходів:

На наведеній вище діаграмі ми бачимо, що коли поточний стан дорівнює q0, на вході 0 наступним станом буде q0 або q1, а на вході 1 наступним станом буде q1. Коли поточний стан дорівнює q1, на вході 0 наступним станом буде q2, а на вході 1 наступним станом буде q0. Коли поточний стан дорівнює q2, на вході 0 наступним станом є q2, а на вході 1 наступним станом буде q1 або q2.

список до масиву java

приклад 2:

NFA з ∑ = {0, 1} приймає всі рядки з 01.

рішення:

Таблиця переходів:

приклад 3:

NFA з ∑ = {0, 1} і приймати всі рядки довжиною принаймні 2.

рішення:

Таблиця переходів: