Non-deterministic Finite Automaton

$M=\left(Q,\Sigma ,\partial ,q_0,F\right)$

• $Q$ = set of states
• $\text{Upsigma}$ = input alphabet: $\lambda \ne \Sigma$ (empty string not in alphabet)
• $\partial$ = transition function
  • 1. transition to multiple states on the same letter
  • transition on empty string
• $q_0$ = initial state
• $F$ = set of accepting states

• Here, a could take you down either path by choosing the transition
• This is why this is non-deterministic

An NFA accepts a string:

• If there is a computation of the NFA that accepts the string. If so, the input string is in the language. An NFA rejects a string:
• If there is no computation of the NFA that accepts the string.
  • The input cannot be consumed
  • Or the final state is in an error state and all the input was consumed

Note

We use this idea to translate ReGex into these finite automoton. We use NFAs as an intermediate step, and them simplify them into a DFA.

Are these more powerful than DFAs? No, they are the same and we know this because we can translate an NFA into a DFA.

• NFA states are labelled with numbers
• DFA states are labelled with letters. DFA might have exponentially more states than the NFA.

You can see how this is formed from ReGex or gets transformed into Deterministic Finite Automaton through Finite Automaton Translations.

Epsilons

NFA’s use a ton of epsilons, the idea is that we want to make things non-deterministic??
When given a choice to use an $ϵ$ or just branch a single note into multiple modes through a deterministic mean… Use an $ϵ$ to get into an intermediary state before doing the deterministic thing.

There are rules for using epsilons for different operators…

Union

Create:

• A new start state with $ϵ$ transitions to the start states of the sub-NFAs
• A new accepting state that each sub-NFA connects to by an $ϵ$ transition.

Kleene Star

Use an $ϵ$ transition for:

• Going directly from start to accept (the “zero repetitions” case).
• Looping back from the accept of the inner NFA to its start (the “repetition” case).
• Entering and exiting the inner NFA nondeterministically.

Concatenation

• This is what I was talking about, we use an $ϵ$ to transition between sub NFAs without consuming input