TechCodeview

• NFA означава недетерминирани крайни автомати. Лесно е да се конструира NFA отколкото DFA за даден нормален език.
• Крайните автомати се наричат ​​NFA, когато съществуват много пътища за конкретен вход от текущото състояние към следващото състояние.
• Всеки NFA не е DFA, но всеки NFA може да бъде преведен на DFA.
• NFA се дефинира по същия начин като DFA, но със следните две изключения, съдържа множество следващи състояния и съдържа ε преход.

На следващото изображение можем да видим, че от състояние q0 за вход a, има две следващи състояния q1 и q2, по подобен начин, от q0 за вход b, следващите състояния са q0 и q1. По този начин не е фиксирано или определено, че с конкретен вход къде да продължим. Следователно тази FA се нарича недетерминистични крайни автомати.

Официално определение на 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 може да бъде представено чрез диграфи, наречени диаграма на състоянието. В който:

mylivecricket в

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.

Пример 2:

NFA с ∑ = {0, 1} приема всички низове с 01.

Решение:

Преходна таблица:

Пример 3:

NFA с ∑ = {0, 1} и приема всички низове с дължина най-малко 2.

Решение:

Преходна таблица: