Theory of Computation

Running head: THEORY OF COMPUTATION
Theory of computation
Name of the Student
Name of the University
Author’s Note

1
0
q0 q1 q2
0
1
0 1
1
THEORY OF COMPUTATION
Answer to Question 1: (Deterministic Finite Accepters)
Problem 1:
0001, 01001 are accepted by the dfa
Problem 2:
For For  = {a, b} construct dfa’s that accepts the sets consisting of
a. all strings with exactly one a
b. all strings with at least one a

2
a a a a
b b a,b
b
b
q0 q1 q2 q3 q4+
THEORY OF COMPUTATION
c. all strings with no more than 3 a’s
d. all strings with at least one a and exactly two b’s

3
THEORY OF COMPUTATION
e. all strings with exactly two a’s and more than two b’s
Problem 3:
Show that if we change fig 2.6 making q3 a nonfinal state and making q0,q1, q2 final states the
resulting dfa accepts
For any dfa the statement is true. If the final and the non-final states are switched then any of the
string leaving in an accepting state leaves the non-final state because we have switched around

4
THEORY OF COMPUTATION
the different final states. Thus by definition the language that is accepted by the new machine
acts as the compliment of language accepted by original one.
Problem 4:
Generalize the observation in the previous exercise. Specifically, show that if M=Q,∑,∂,q0,F and
It is proved by contradiction suppose M is not a minimal DFA for X then there exists another
DFD Z for A such that Z has fewer states than M. Another DFD Z’ is created by swapping the
acceptance and non-acceptance states of Z. The Z’ recognizes the complement of X. But the
complement of X is just X’ so Z’ recognizes X. Z’has the same number of states as Z and M has
same number of states as M. Thus if it is assumed that Z has strictly fewer states than M then Z’
has strictly fewer states than M, then Z’would have strictly fewer states than M. But since Z’
recognizes X, this contradicts our assumption that M is minimal DFA for X. Therefore M is a
minimal DAA for X.
Problem 5:
a. Dfa for the languages L= {ab5wb2 : w  {a, b}*}
b. Dfa for the languages L = { abnam : n ≥ 2, m ≥ 3}

5
THEORY OF COMPUTATION
c. Dfa for the languages L= {w1abw2 : w1  {a, b}*, w2  {a, b}*}
d. Dfa for the languages L= {ban:n ≥1,n≠5}
Problem 9:
Consider the sets of strings on {0, 1} defined by the requirements below. Construct dfa’s.
a. Every 00 is followed immediately by a 1