Nondeterministic Finite-state Automata

Can have multiple state from one state given an input
The transition function $f$ assigns a set of states to each pair of state and input (so that $f : S \times I \to P (S)$ )

Let a string $x = x_{1} x_{2} \dots x_{k}$ input to an NFA.
The first input symbol $x_{1}$ takes the starting state $s_{0}$ to a set $S_{1}$ of states
The next input symbol $x_{2}$ takes each of the states in $S_{1}$ to a set of new states.
- Let $S_{2}$ be the union of these sets.
Repea, at each stage, all states obtained using a state obtained at the previous stage and the current input symbol
The string $x$ is accepted if there is at least 1 final state in the set of all states using $x$ .
The language recognized by a NFA is the set of all strings recognized by this NFA.
theorem
- If the language $L$ is recognized by a NFA, $M_{0}$ , then $L$ is also recognized by a DFA $M_{1}$
  - where $M_{1}$ (deterministic) is converted from $M_{0}$ (Non-deterministic)
  - $M_{1}$ ‘s states are created from combinations of possible states reached by $M_{0}$ ‘s states
    - with OR operation
    - combination states where each state can have multiple possible states, the new state of $M_{1}$ is all of those possible states.

StrixTheKiet Notes