ITS64304 Tutorial – 3 NFAs and DFAs 1
Bachelor of Software Engineering (Hons)
Bachelor of Computer Science (Hons)
ITS64304: Theory of Computation
Tutorial – 3: NFAs and DFAs
Aim
The aim of this tutorial is to learn analysis and design of finite state machines. By the end of this
tutorial you should be able to design appropriate NFA and/or a DFA for a given specification, and
trace a computation for a given string. (Aligns with Module Learning Outcome 2)
Taylor’s Graduate Capabilities (TGCs) developed
3.1 Finite State Automata
Example
Give a regular expression and an equivalent NFA for the language over {a, b} that starts with aa
and contains the substring ba. Convert the NFA you obtained to a DFA.
Solution
Regular Expression: aa(a υ b)* ba (a υ b)*
NFA:
a, b
a a b
a
a, b
ITS64304 Tutorial – 3 NFAs and DFAs 2
DFA:
Questions
1) Build an NFA (separately for each) that accepts the following languages.
a) Strings over the digits 0-9 which contain at least three 1’s.
b) Strings over the digits 0-9 which contain 777 somewhere in the string.
c) Strings over the digits 0-9 which do not contain 777 anywhere in the string.
d) Strings over the digits 0-9 which have length 5 or less.
2) Obtain a DFA for each of the NFA built in 1) above.
3) Give a regular expression for each of the sets given below and build an equivalent NFA.
a) The set of strings over {a, b, c} in which all the a’s precede the b’s, which in turn
precede the c’s.
b) The set of strings over {a, b, c} that begin with a, contain exactly two consecutive b’s
and end with cc.
c) The set of strings over {a, b, c} that do not contain the substring aa.
Reflection
Constructing a NFA or a DFA for a given specification, which is easier for you to derive? Can you
minimize a given DFA?
a a b a
a
ε
b b
b
a, b