Computation Theory 3: Nondeterministic and Deterministic

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 MD with the following definition:

  • Q = {S1}
  • Σ = {0}
  • δ(S1, 0) = S1
  • q0 = S1
  • F = {S1}.

Draw the state diagram of M.  By the definition of M we have that we will always be on state S1 and following path 0 we will always land on S1.  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 MND:

  • Q = {S1, S2}
  • Σ = {0}
  • δ(S1, 0) = S1, δ(S1, 0) = S2, δ(S2, 0) = S1
  • q0 = S1
  • F = {S1}.

When the computation is on the state S1 and 0 is applied we don’t know if we will end up on state S1 or S2. 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 S1 of MND?

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 MND for following the path leading back to S1 and one for the path leading to S2. For the next step of the computation we would apply 0 to each of the copies of MND. The copy that starts at S1 would split again, one path going back to S1 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 MND. One copy has the path 00 looping on S1 twice. The next copy has the path lopping on S1 once and the going to S2. The last copy has the path going to S2 then back to S1.

Does our automata MND 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 MND accepting 00 is that 00 lands on an accept state. S1 is the accept state for MND and in two of the possible outcomes for 00 we land on the accept state. So MND accepts 00.

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

  • Q = {S1, S2, S3}
  • Σ = {0}
  • δ(S1, 0) = S2, δ(S1, 0) = S3, δ(S2, 0) = S2, δ(S3, 0) = S3
  • q0 = S1
  • F = {S1}.

Again we start at S1 and end up with two copies of MND2. The first takes path 0 to S2 and the second takes the path 0 to S3. The next step for both copies loops back to the state that it’s on. The accept state is still S1 so MND2 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, Σ, δ, q0, 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.

  1. Construct your own finite automaton by using a state diagram and a formal definition.
  2. What does it mean for a finite automaton M to accept a string?
  3. What is the language of a finite automaton M?
  4. Determine the language of the finite automaton MD 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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s