Nondeterministiske Endelige Automater¶
En NFA M accepterer et input w hvis M ved at læse w KAN havne i en accepttilstand til sidst.
Note
Hvis en NFA ingen steder har at gå, "crasher" den, og læser dermed ikke strengen.
Definition¶
En nonderterministisk endelig automat (NFA) er en 5-tupel. $$ (Q,\Sigma,\delta,q_0,F) $$ Q: endelig mængde af tilstande
\Sigma: input alfabet
\delta: overføringsfunktion
q_0: starttilstand q_0 \in Q
F: mængde af accepttilstande F \subseteq Q
Transitioner beskriver mængden af mulige efterfølgertilstande for ethvert tegn.
\delta(q_1,a)=Ø
\delta(q_2,a)=\{q_1,q_2\}
\delta(q_1,\varepsilon)=\{q_2\}
\delta(q_2, \varepsilon)=Ø $$ \delta:Q\times\Sigma_\varepsilon \rightarrow \mathcal{P}(Q) $$ - mængden af alle delmængder af Q
Ækvivalens mellem DFA og NFA¶
NFA'er og DFA'er er ækvivalente:
For enhver NFA N kan vi konstruere en DFA M så: L(N)=L(M)
Eksempel 1:
Eksempel 2:
Lukning Under de Regulære Operationer¶
Foreningsmængden¶
Konkatination¶
Stjerneoperationen¶
