CmSc 365 Theory of Computation

Finite State Automata (Finite State Machines)
NonDeterministic Finite State Automata
Description of a non-deterministic FSA

An incompletely specified FSA is one whose transition function is not defined on all pairs (q,a),
where q is a state, a is a symbol from the alphabet.

A nondeterministic FSA is one, where for some state q and a symbol a we may have more than one transition. Here we do not have a transition function, as all functions have to specify unique images.
Here we have a transition relation Í K x { ∑ È e } x K.

Note that the empty symbol is included in the transition relation.

Example:

This FSA accepts ( ab U aba)*

In state q1 there is a choice. We can either read a and go to q0 or simply “jump” to q0 without reading a symbol. Note that this FSA is incomplete. Depending on the choice the final state may not be reached for a string, that is intended to be accepted by the FSA. However, there is a possible sequence of choices, such that the final state is reached for that string.

Definition: A deterministic finite automaton is a quintuple M = (K, ∑, Δ, s, F), where

K is a finite set of states
∑ is an alphabet
s є K is the initial state
F Í K is the set of final states
Δ is the transition relation, a subset of K x (∑ È e) x K

A transition is a triple (q, u, p), where q and p are in K, and u is in ∑ È e.
If a transition (q, e, p) is followed, no input symbol is read.

A configuration is any element (q,w) in K x ∑*

Definition: If (q,w) and (q',w') are two configurations,
then (q,w) yields (q',w') in one step if and only if w = uw', where u є ∑ È e, and (q, u, q' ) є Δ.

This is written as:

(q,w) ├ M (q',w')

(q,w) ├ M* (q',w') means that (q,w) yields (q',w') after some number of steps. ├ M* denotes the transitive closure of ├.

 

Definition: A string w є ∑* is said to be accepted by M
iff there is a state q є F such that (s,w) ├ M* (q,e)

Definition: The language accepted by M, L(M), is the set of all strings accepted by M.

So we say that a non-deterministic FSA accepts a string, if there is a possible path of transitions from the initial state to a final state for that string.

In summary there are two essential differences between deterministic and non-deterministic automata:

  1. Deterministic FSAs are defined with a transition function, while nondeterministic FSAs are defined with transition relation
  2. Each transition in a deterministic FSA is upon reading a symbol from ∑, while in a non-deterministic FSA there may be transition upon the empty symbol (such transitions are usually called “jumps”)

There is a theorem stating that for each nondeterministic FSA there is an equivalent deterministic FSA.

Learning Goals
  • Be able to distinguish between a deterministic and a nondeterministic FSA

Exam-like questions and problems
  1. Where is the difference between a deterministic FSA and a non-deterministic FSA?
  2. When do we say that a non-deterministic FSA accepts a string?
  3. Construct an FSA that accepts each of the following sentences:
    1. Tom is a banker.
    2. Tom is a rich banker
    3. Tom is happy
    4. Tom is very happy
    5. Tom is a rich banker and is very very happy.

      6. Consider each word as a symbol in an alphabet.
      What other sentences would be accepted by the FSA?

  4. Problems: 2.2.1, 2.2.2, 2.2.3 in the textbook.
Back to Contents page
Created by Lydia Sinapova