nfa.md

Non-deterministic Finite Automata

Definition

Formal

• 5 tuple (Q, Σ, q0, A, δ)
  • Q is finite state of inputs
  • Σ is alphabet
  • (q0 ∈ Q) is the initial state
  • (A ⊆ Q) is the set of accepting states
  • (δ: Q x (Σ ∪ {λ}) -> (Q)(λ) is the transition function

Informal

• A NFA can have multiple possible transitions for each symbol / state combo.
• Possible to have epsilon (λ) transitions, this means that the state can change to a new state without reading any inputs at all.

Example

Here is a NFA for the regular expression a*(a|b)ba* | a*

No epsilon (λ or ε) transitions here, we know it's nfa because from state (1) there's two possible transitions you can take upon reading an (a).

NFA to DFA conversion

Here is a random NFA

Start at initial state, mark down all states that can be reached from this state using epsilon (λ or ε) transitions (state itself is always reachable)

Initial state = 1

Reachable from 1 by epsilon (λ or ε) = {1,2,3}

Therefor for our DFA {1,2,3} is our initial state.

State	0	1
({1,2,3})	({2,4})	({2,4})
({2,4})	({3,2})	({2,4})
({3,2})	({4})	({2,4})
({4})	({3,2})	{ }