BCCC Computer Science Theory NFA DFA and Proofs Problems

Problem 10
q4
1
1
q0
0
q3
0
1
1
q1
1
0
q2
0
1. (3 points.) The DFA state diagram above is defined on the alphabet ⌃ = {0, 1}. Write out
its formal definition (as a 5-tuple). When specifying the transition function , you can draw
a table or simply describe the output of for all states on all possible inputs.
2. (3 points.) Describe the language recognized by the DFA in one or two sentences, then explain
why the DFA accepts a string if and only if it matches your description. [Hint: Test some
strings and look for a pattern; never forget the empty string ✏!]
Rationale: The goal of this question is to make sure you’re comfortable reading state diagrams, evaluating DFAs
on strings, and reasoning about what they do.
References: Sipser 1.1 pp. 34-37; Lightning review of DFAs from the Resource Archive section of the course
webpage.
2
Problem 2.
1. (4 points.) Consider the DFA drawn below. What is the language recognized by this DFA
(over what alphabet)? Describe your reasoning.
c
a
b
b
q1
c
q2
c
q3
a, b
a
q4
a, b, c
2. (4 points.) The DFA drawn below recognizes all strings over the alphabet {1, 2, 3} that end
in a 1 or a 3 and don’t contain 1’s and 3’s adjacent to each other (that is, the substrings 13
and 31 are forbidden). Draw a DFA state diagram that recognizes the same language (that
is, accepts exactly the same set of strings over {1, 2, 3}) but which has at most four states
in total.
Explain in words why your DFA recognizes the same language as the pictured DFA.
1
q1
3
q4
1, 2, 3
q5
1, 2, 3
1
1
q0
2
q2
2
3
3
2
2
q3
1
3
Rationale: More practice reading state diagrams and evaluating DFAs on strings; also, practice designing DFAs
to perform a task and simplifying them.
References: Sipser 1.1 pp. 34-37 (DFAs); Sipser 1.1 pp. 41-43 (designing DFAs); Lightning reviews of DFAs and
designing DFAs from the Resource Archive section of the course webpage.
3
Problem 3
1. (4 points). In binary, the natural numbers are 0, 1, 10, 11, 100, 101, …, etc. Draw a state
diagram for an NFA on the alphabet ⌃ = {0, 1} that recognizes the language of binary
natural numbers divisible by 4. (For instance, your machine should accept 100, but reject 11
and 101. Reject strings with extra leading zeroes, like 0100.)
Explain in words why your NFA recognizes the language specified.
2. (2 points). Over the binary alphabet {0, 1}, Let L1 be the language of all strings whose length
is divisible by 3, and L2 be the language of all strings that have an even number of 0’s. The
state diagram below depicts an NFA that recognizes L1 [ L2 .
Specify the elements of a 5-tuple (Q, ⌃, , q0 , F ) equivalent to the NFA state diagram below.
When specifying the transition function, feel free to specify only for inputs that transition
to a non-empty set of states; for the others, you can assume maps to ;. No justification
required.
1
1
0
q1
q2
0
✏
q0
✏
0, 1
q3
0, 1
q4
0, 1
q5
3. (4 points). Draw the state diagram of a DFA over {0, 1}, with at most 6 states, that also
recognizes L1 [ L2 . Explain in words why your DFA recognizes this language. (We’ll discuss a
general procedure for converting NFAs to DFAs in Lecture 3, but this question doesn’t require
it.)
Rationale: The purpose of this question is to get experience in building, testing, and simplifying NFAs, as well
as converting NFAs to DFAs.
References: Sipser 1.2 pp. 47-53 (NFAs), also see the Lightning Review video on NFAs in the Resource Archive
section of the course webpage.
4
Problem 4
1. (2 points.) Recall that the (Kleene) star operation is defined as follows:
A⇤ = {x1 x2 . . . xk | x1 , x2 , . . . , xk 2 A, k
0}.
Let A and B be regular languages. Is it true that (A [ B)⇤ and A⇤ [ B ⇤ are the same
language? If so, provide a proof. If not, provide a counterexample. (Recall the order of
operations: A⇤ [ B ⇤ = (A⇤ ) [ (B ⇤ ).)
2. (2 points.) Let A be a regular language. Is it true that A⇤ A⇤ and (AA)⇤ are the same
language? If so, provide a proof. If not, provide a counterexample.
Some practice reasoning about the regular operations.
References: Sipser p.44-45 (definition of Union, Concatenation, and Star, as well as closure).
5
Problem 5
1. (6 points.) Given a language A over an alphabet ⌃, define doub(A) as follows:
doub(A) := {w1 w1 w2 w2 . . . wn wn | w1 w2 . . . wn 2 A; w1 , w2 , . . . , wn 2 ⌃}.
That is, each string in doub(A) can be obtained by beginning with some string w1 w2 . . . wn in
A and replacing each character with two copies of itself.
Show that the class of regular languages is closed under the operation doub by explaining
how to modify an arbitrary DFA D1 so that it recognizes the language doub(L(D1 )). For
simplicity, you may consider just the case in which the alphabet is ⌃ = {0, 1}.
2. (2 points.) Given a language A over an alphabet ⌃, define oct(A) similarly to doub(A), except
that we now replace each character with eight copies of itself.
Show that the class of regular languages is closed under the operation oct by reasoning from the
fact that the regular languages are closed under other, previously proved, regular expressions.
(That is, prove without explaining how to modify a DFA.) You may assume that doub is
regular.
Rationale: The point of this question is to practice proving regularity of operations using various techniques.
References: Sipser pp.45-46 for an example of constructing a DFA that recognizes A1 [ A2 , given DFAs that
recognize A1 and A2 ; for part 2 Sipser p.44-45 (definition of Union, Concatenation, and Star, as well as closure).
6