Epsilon transitions

The finite machine below recoginizes strings that contain a repeated pattern.

The machine accepts any string that contains 1 or more repetitions of the substring 011. To make it possible for the machine to accept inputs that contain more than one repetition of the pattern 011 the machine makes use of a special type of transition called an epsilon transition.

Nondeterminism

Epsilon transitions make a machine nondeterministic. When a machine enters a state that has an epsilon transition coming from it, the machine can decide whether to stay in that state and await the next input symbol, or it can immediately take the epsilon transition and go a new state.

A nondeterministic finite automaton, or NFA, accepts its input if there is some path through the machine driven by the input that results in the machine making it to an accepting state.

Another example

The machine below accepts any input string that contains the substring 101 or the substring 010.

The machine uses the two epsilon transitions coming from state 1 to guess when either the pattern 101 or the pattern 010 is about to start. If the machine guesses correctly and can make it to the end state, the machine will accept the input.

Ambiguous transitions

Here is another machine that accepts the same input language as the previous machine.

This machine features ambiguous transitions. A transition is ambiguous if it comes from a state that has more then one transition coming from it driven by the same input symbol. When the machine enters an ambiguous state it can guess which one of the transitions coming off of that state to take. If the machine guesses correctly and can make it to a final state, the machine accepts the input.

An NFA is a finite machine that includes epsilon transitions and/or ambiguous transitions.

Formal definition

A nondeterministic finite automaton is a tuple {Q, Σ, δ, q0, F } where

  1. Q is a finite set called the states,
  2. Σ is a finite set called the alphabet,
  3. δ : Q × Σε → P(Q) is the transition function,
  4. q0 ∈ Q is the start state, and
  5. F ⊆ Q is the set of accept states.

Converting NFAs to DFAs

The epsilon closure E(q) of a state q in Q is the union of the set {q} with the set of all states that can be reached from q via one or more ε transitions.

If R is a set of states from Q, the epsilon closure E(R) is defined as the union of the epsilon closures of all the states in R.

How to convert an NFA to a DFA:

  1. The set of states of the DFA is P(Q), the power set of states Q in the original NFA.
  2. The start state of the DFA is E({q0}), where q0 is the original start state of the NFA.
  3. For sets R in P(Q) and input characters c ∈ Σ, the transition function δ of the DFA is defined in terms of the transition function δ of the NFA by

The set of accepting states F of the DFA is defined to be the set of all states containing at least one final state of the NFA.

Example

Convert the NFA depicted below into a DFA.

Step 1: make a state for each possible subset of the set of states. Label a state a final state if at least one of the states in the subset is a final state.

Step 2: add the transitions.