**Introduction:**

In this module we are going to continue talking about properties of finite automata. There are two concepts are going to go over, nondeterministic and deterministic. The background you need for this module is an understanding of the definition of finite automata. If you’re unsure about your understanding go back and review Computation Theory Module 1.

**Deterministic Finite Automata:**

We are going to start by looking at deterministic finite automata. In plain terms a deterministic computation is one that will always have the same output given the same input. That is given the input parameters and current state we know what the outcome will be. Lets consider a simple example.

Suppose we have a finite automata M_{D} with the following definition:

- Q = {S
_{1}} - Σ = {0}
- δ(S
_{1}, 0) = S_{1} - q
_{0}= S_{1} - F = {S
_{1}}.

Draw the state diagram of M. By the definition of M we have that we will always be on state S_{1} and following path 0 we will always land on S_{1}. This is a deterministic finite automata. In a deterministic finite automata there will always be exactly one exit path per alphabet element per state. We refer to deterministic finite automata as DFA.

**Nondeterministic Finite Automata:**

Nondeterministic computation lacks the property that we can tell what the outcome of the computation will be given the input and current state. This is easiest to understand with an example.

Consider the following definition of a finite automata M_{ND}:

- Q = {S
_{1}, S_{2}} - Σ = {0}
- δ(S
_{1}, 0) = S_{1}, δ(S_{1}, 0) = S_{2}, δ(S_{2}, 0) = S_{1} - q
_{0}= S_{1} - F = {S
_{1}}.

When the computation is on the state S_{1} and 0 is applied we don’t know if we will end up on state S_{1} or S_{2}. Therefore we don’t know what the outcome of the computation will be. We refer to nondeterministic finite automata as NFA.

**Nondetermistic Computation:**

So how do we perform computation in with an NFA? Try to formulate your own theory of what happens. Specifically ask yourself what do we do when faced with an input of 0 at state S_{1} of M_{ND}?

We end up making copies of the NFA for each possible path of execution. For example if we were given the string 00 we would make a copy of M_{ND} for following the path leading back to S_{1} and one for the path leading to S_{2}. For the next step of the computation we would apply 0 to each of the copies of M_{ND}. The copy that starts at S_{1} would split again, one path going back to S_{1} and one going to S2. Draw each one of the copies to keep track of what’s going on. You should have three copies of M_{ND}. One copy has the path 00 looping on S_{1} twice. The next copy has the path lopping on S_{1} once and the going to S_{2}. The last copy has the path going to S_{2} then back to S_{1}.

Does our automata M_{ND} accept the string 00? Make a list of reasons why or why you think 00 is accepted or not accepted. Recall that the definition of M_{ND} accepting 00 is that 00 lands on an accept state. S_{1} is the accept state for M_{ND} and in two of the possible outcomes for 00 we land on the accept state. So M_{ND} accepts 00.

Now lets look at an example where the string is not accepted. Consider the finite automata M_{ND2} with the following definition:

- Q = {S
_{1}, S_{2}, S_{3}} - Σ = {0}
- δ(S
_{1}, 0) = S_{2}, δ(S_{1}, 0) = S_{3}, δ(S_{2}, 0) = S_{2}, δ(S_{3}, 0) = S_{3} - q
_{0}= S_{1} - F = {S
_{1}}.

Again we start at S_{1} and end up with two copies of M_{ND2}. The first takes path 0 to S_{2} and the second takes the path 0 to S_{3}. The next step for both copies loops back to the state that it’s on. The accept state is still S_{1} so M_{ND2} does not accept 00.

With that in mind lets take a look at the formal definition of a nondeterministic finite automaton:

A nondeterministic finite automaton is a 5-tuple (Q, Σ, δ, q_{0}, F) such that:

- Q is a finite set of states.
- Σ is a finite alphabet.
- δ: Q × Σ
_{ε}→ P(Q) - q0 ∈ Q the start state.
- F ⊆ Q the accept states.

The set P(Q) is the powerset of Q, which is the set of all subsets of Q. Which is a formal way of saying that a state can have paths of the same alphabet letter to multiple states. We also have a new path letter ε for nondeterministic finite automata. When a state has a path labeled ε starting at it the path is always taken making another copy of the automaton as if it were labeled as the path entry in the δ function.

**Unary Alphabet:**

One property that all of the finite automata share in this module is something called a unary alphabet. A finite automata has a unary alphabet when there is only one symbol in the alphabet.

**Conclusion:**

To wrap up this section lets have an impromptu quiz. If you have trouble with the following questions go ahead and review the material from the previous modules.

- Construct your own finite automaton by using a state diagram and a formal definition.
- What does it mean for a finite automaton M to accept a string?
- What is the language of a finite automaton M?
- Determine the language of the finite automaton M
_{D}of this section.

The second part of testing your understanding is write out an explanation of the material we have covered so far. Don’t write it as though you’re writing it for me, or for someone reading this material. Write it as though you are going to explain it to a student who has never studied mathematics or computers. Try to imagine what their questions would be and how you would answer them.