Suggest edit — Non-deterministic Finite Automata

Title

Name

Note

---
title: "Non-deterministic Finite Automata"
type: concept
related: [Alphabet, Deterministic Finite Automata, Nondeterministic Finite Automata]
source: https://www.jemoka.com/posts/kbhnondeterministic_finite_automata/
confidence: high
status: active
---

NFA is a relaxation of DFA, but which is allowed to make non-deterministic &ldquo;verified guesses&rdquo;.
this is basically a DFA, but our new machine accepts a string if there exists some path that reaches some accept state from some start state.
at each state, we can have any number of out arrows for some letter $\sigma \in \Sigma$, including for the empty string $\varepsilon$. meaning we can move between states without doing anything.
we (Omer) allows multiple NFA start states (Spiser only allows one). we can convert between these easily just by having an epsilon (empty string) transition stuck between the &ldquo;single&rdquo; start state and the multiple start states.
constituents A NFA is a five-tuple $N = (Q, \Sigma, \delta, Q_{0}, F)$, whereby:
$Q$ is the finite set of all states $\Sigma$ is the alphabet $\delta: Q \times \Sigma_{\varepsilon} \to 2^{Q}$ (where $\Sigma_{\varepsilon} = (\Sigma \cup \{\varepsilon\})$, with $\varepsilon$ being the empty string); the output is a boolean assignment of whether or not we can reach each state, because note you are now allowed multiple edges between states $Q_0 \subseteq Q$ which is the set of start states $F \subseteq Q$ remains the set of accept states requirements accept Let $w_1, &hellip;, w_{n} \in \Sigma$, and $w = w_1 &hellip; w_{n} \in \Sigma^{*}$, $M$ accepts $w$ if there exists $r_0, &hellip;, r_{n} \in Q$ such that:
$r_{0} \in Q_{0}$ $r_{i+1} \in \delta(r_{i}, w_{i+1})$ for all $i=0, &hellip;, n-{1}$, and $r_{n} \in F$ additional information NFAs are usually simpler than DFAs &hellip;because you don&rsquo;t have to specify all edges; non-specified transitions means the can be automatically rejected
DFAs are equivalent to NFAs we want to show that DFAs recognize the same set of languages as NFAs. in other words, does not add power for finite automata&hellip; &ldquo;finite memory is very robust&rdquo;.
we want to define the subset construction; tho goal here is that given a particular NFA named $N$, we desire to find a particular DFA named $M$ which recognizes the same language.
insight: DFA and NFAs are markovian! instead of monitoring all the different paths you take, we only monitor all the possible states you could have reached&mdash;this is, then, only exponential in the number of states.
we therefore do computation in parallel on the set of all possible states that could be reached thus far. at each step, then, a DFA you defined from an NFA has a state space of $Q&rsquo; = 2^{Q}$. Each of your states, then, is some subset of possible states in the original NFA.
epsilon closure to deal with epsilon steps (i.e. steps where you do nothing and advance), you have to first define the epsilon closure:
for a subset of states $S \subseteq Q$, the $\varepsilon$ closure of $S$ is:
\begin{equation} \varepsilon (S) = \qty {q | q\ \text{reachable from some}\ s \in S\ \text{by taking one or more $\varepsilon$ transitions}} \end{equation}
and now, onto the construction that DFAs are equivalent to NFAs
proof $Q&rsquo;=2^{Q}$ $\delta&rsquo;: Q&rsquo; \times \Sigma \to Q&rsquo;$, specifically $\bigcup \varepsilon \qty(\delta\qty(r, \sigma)), r\in R$, where $R \in Q&rsquo;$ is one of our conjoined-states that is, we apply every transition we can on the states that we have, and union all of their results together $F&rsquo; = \qty {R \in Q&rsquo; | f \in R\ \text{for some}\ f \in F}$, that is, the subset of the conjoined states for which there is a single member in the conjoined state that&rsquo;s active that is also an accept state $q_0&rsquo; = \varepsilon (q_0)$ NFA also recognizes exactly regular languages that is, DFA and NFA recognizes the same types of languages