CSci 301 Lecture Notes

Week One, Thursday: Nondeterminism

A DFA in a given state reads an input symbol. We know its next state, determined by the state transition function. This is called deterministic computation. Nondeterminism is a generalization of determinism: several choices may exist at any "point" (step) in the computation.

DFA: Has only one choice for each input symbol. Doesn't move on epsilon.
NFA: May have many choices for each input symbol (a set of states, including the empty set). Input symbols include epsilon.

Examples 1.14, 1.15, and 1.16.

Formal Definition of an NFA

Let P(Q) be the power set of Q:

A nondeterministic finite automaton is a 5-tuple (Q, S, d, q₀, F), where

Q is a finite set called the states.
S (capital Sigma) is a finite set called the alphabet.
d (lowercase delta) is a mapping from Q x (S union epsilon) to P(Q) called the transition function.
q₀ is the start state, an element of Q.
F is a subset of Q called the set of accept states.

Example 1.18.

The formal definition of computation for an NFA is similar to that of a DFA: A machine accepts its input if all the input is consumed and the machine ends in an accept state.

Equivalence of NFAs and DFAs

Theorem 1.19, proof idea and proof.

Example 1.21.

Closure under the Regular Operations

Theorems 1.22, 1.23, and 1.24.

Homework Assignment

Assigned Thursday, September 10, due Thursday, September 17, at beginning of class.

Chapter 1: Exercises 1.1, 1.2, 1.3, 1.4, 1.5.

Email: Richard dot J dot Wagner at gmail dot com