TechCodeview

• НФА је скраћеница од недетерминистичких коначних аутомата. Лако је конструисати НФА него ДФА за дати регуларни језик.
• Коначни аутомати се називају НФА када постоји много путања за одређени унос из тренутног стања у следеће стање.
• Сваки НФА није ДФА, али сваки НФА се може превести у ДФА.
• НФА је дефинисан на исти начин као и ДФА, али са следећа два изузетка, садржи више следећих стања и садржи ε прелаз.

На следећој слици можемо видети да из стања к0 за улаз а постоје два следећа стања к1 и к2, сходно томе, из к0 за улаз б, следећа стања су к0 и к1. Дакле, није фиксирано или одређено да са одређеним уносом где даље. Стога се овај ФА назива недетерминистичким коначним аутоматима.

Формална дефиниција НФА:

НФА такође има пет стања истих као ДФА, али са различитом функцијом транзиције, као што је приказано у наставку:

 &#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 

Графичко представљање НФА

НФА се може представити диграфима који се називају дијаграм стања. У којима:

1. Држава је представљена врховима.
2. Лук означен улазним карактером приказује прелазе.
3. Почетно стање је означено стрелицом.
4. Коначно стање је означено двоструким кругом.

Пример 1:

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

Решење:

Прелазни дијаграм:

Табела прелаза:

У горњем дијаграму можемо видети да када је тренутно стање к0, на улазу 0, следеће стање ће бити к0 или к1, а на 1 улазу следеће стање ће бити к1. Када је тренутно стање к1, на улазу 0 следеће стање ће бити к2, а на 1 улазу следеће стање ће бити к0. Када је тренутно стање к2, на 0 улазу следеће стање је к2, а на 1 улазу следеће стање ће бити к1 или к2.

Пример 2:

НФА са ∑ = {0, 1} прихвата све стрингове са 01.

Решење:

Табела прелаза:

Пример 3:

НФА са ∑ = {0, 1} и прихвати све низове дужине најмање 2.

Решење:

Табела прелаза: