# 1.2 nondeterminism

• Determinism(DFA) is a subset of nondeterminism(NFA).
• For each letter in DFA, it could only be on only one arrow.
• NFA may have $\varepsilon$ on the arrow，means one or many arrows may exit from this state(zero).
• If a string in a branch is accepted, then NFA accepts the input string.

## Formal Def of NFA

A nondeterministic finite automation is a 5-tuple($Q, \Sigma, \delta, q_0, F$), where:

• $Q$ is a Finite set of states
• $\Sigma$ is a finite alphabet
• $\delta : Q \times \Sigma_{\varepsilon} \rightarrow P(Q)$ is the transition function
• $q_0 \in Q$ is the start state
• $F \subseteq Q$ is the set of accept states

Formal Def of computation for an NFA:

Let N=($Q, \Sigma, \delta, q_0, F$) be an NFA and $w$ a string over the alphabet $\Sigma$. Then we say that N asscepts $w$ if we can write $w$ as $w=y_1 y_2 \cdots y_m$, where each $y_i$ is a member of $\Sigma_{\varepsilon}$ and a sequence of states $r_0, r_1, \cdots, r_m$ exists in $Q$ with the following three conditions:

• $r_0 = q_0$
• $r_{i+1} \in \delta (r_i, y_{i+1}) \text{ , for } i=0, \cdots, m-1$
• $r_m \in F$

## Equivalence of NFAs & DFAs

Two machines are equivalent if they recognize the same language.

Every nondeterministic finite automation has an equivalent deterministic finite automation.

### Convert NFA to DFA

From start state.

For each state and each alphabet a, create a new state(the combination of all possible state using this character), and make a transition from this state to the new state.

For the combination state, if any of the state inside of it has the certain transition, then it counts for the transition.

## $\varepsilon-NFA$

### Convert $\varepsilon-NFA$ to DFA

First find the $\varepsilon$ closure of start state.

For each state, find the next state using the same method as NFA to DFA. But this state should be the combination of all states' $\varepsilon$ closure.