CmSc 365 Theory of Computation
Finite State Automata (Finite State Machines)
An incompletely specified FSA is one whose transition function
is not defined on all pairs (q,a),
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.
Note that the empty symbol is included in the transition relation.
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
A transition is a triple (q, u, p), where q and p are in K, and u is in ∑ È e.
If (q,w) and
(q',w') are two configurations,
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
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:
There is a theorem stating that for each nondeterministic FSA there is an equivalent deterministic FSA.
Exam-like questions and problems
Back to Contents page
Created by Lydia Sinapova