TechCodeview

• NFA står for non-deterministic finite automata. Det er nemt at konstruere en NFA end DFA for et givet regulært sprog.
• De endelige automater kaldes NFA, når der eksisterer mange stier til specifikke input fra den nuværende tilstand til den næste tilstand.
• Hver NFA er ikke DFA, men hver NFA kan oversættes til DFA.
• NFA er defineret på samme måde som DFA, men med de følgende to undtagelser indeholder den flere næste tilstande, og den indeholder ε-overgang.

I det følgende billede kan vi se, at fra tilstand q0 for input a, er der to næste tilstande q1 og q2, ligesom fra q0 for input b er de næste tilstande q0 og q1. Det er således ikke fastlagt eller bestemt, at med et bestemt input, hvor man skal gå videre. Derfor kaldes denne FA ikke-deterministiske endelige automater.

Formel definition af NFA:

NFA har også fem tilstande som DFA, men med forskellige overgangsfunktioner, som vist følger:

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

hvor,

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

Grafisk repræsentation af en NFA

En NFA kan repræsenteres af digrafer kaldet tilstandsdiagram. Hvori:

1. Staten er repræsenteret ved toppunkter.
2. Buen mærket med et inputtegn viser overgangene.
3. Starttilstanden er markeret med en pil.
4. Den endelige tilstand er angivet med den dobbelte cirkel.

Eksempel 1:

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

Løsning:

Overgangsdiagram:

Overgangstabel:

I ovenstående diagram kan vi se, at når den aktuelle tilstand er q0, på input 0, vil den næste tilstand være q0 eller q1, og på 1 input vil den næste tilstand være q1. Når den aktuelle tilstand er q1, vil den næste tilstand på input 0 være q2 og på 1 input, vil den næste tilstand være q0. Når den aktuelle tilstand er q2, på 0 input er den næste tilstand q2, og på 1 input vil den næste tilstand være q1 eller q2.

Eksempel 2:

NFA med ∑ = {0, 1} accepterer alle strenge med 01.

Løsning:

tilføje strenge java

Overgangstabel:

Eksempel 3:

NFA med ∑ = {0, 1} og accepter alle strenge med mindst 2 længder.

Løsning:

Overgangstabel: