• NFA je zkratka pro nedeterministické konečné automaty. Je snadné vytvořit NFA než DFA pro daný běžný jazyk.
• Konečné automaty se nazývají NFA, pokud existuje mnoho cest pro konkrétní vstup z aktuálního stavu do dalšího stavu.
• Každý NFA není DFA, ale každý NFA může být přeložen do DFA.
• NFA je definována stejným způsobem jako DFA, ale s následujícími dvěma výjimkami obsahuje několik dalších stavů a ​​obsahuje přechod ε.

Na následujícím obrázku vidíme, že ze stavu q0 pro vstup a jsou další dva stavy q1 a q2, obdobně ze stavu q0 pro vstup b jsou další stavy q0 a q1. Není tedy pevně dané nebo určeno, že s konkrétním vstupem, kam jít dál. Proto se tento FA nazývá nedeterministický konečný automat.

objekt v Javě

Formální definice NFA:

NFA má také pět stavů stejných jako DFA, ale s jinou přechodovou funkcí, jak je uvedeno níže:

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

kde,

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

Grafické znázornění NFA

NFA může být reprezentován digrafy nazývanými stavový diagram. Ve kterém:

1. Stav je reprezentován vrcholy.
2. Oblouk označený vstupním znakem ukazuje přechody.
3. Počáteční stav je označen šipkou.
4. Konečný stav je označen dvojitým kruhem.

Příklad 1:

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

Řešení:

Schéma přechodu:

Přechodová tabulka:

Ve výše uvedeném diagramu můžeme vidět, že když je aktuální stav q0, na vstupu 0 bude další stav q0 nebo q1 a na 1 vstupu bude další stav q1. Když je aktuální stav q1, na vstupu 0 bude další stav q2 a na vstupu 1 bude další stav q0. Když je aktuální stav q2, na vstupu 0 je dalším stavem q2 a na 1 vstupu bude dalším stavem q1 nebo q2.

css první dítě

Příklad 2:

NFA s ∑ = {0, 1} přijímá všechny řetězce s 01.

Řešení:

Přechodová tabulka:

v řetězci v jazyce Java

Příklad 3:

NFA s ∑ = {0, 1} a přijměte všechny řetězce délky alespoň 2.

Řešení:

Přechodová tabulka: