CS 410 Homework 1
Fall 2006 [Bono]
Due: Friday, Sept. 8, 2pm
Details of submitting will be discussed in lecture.
Problem 1
Give a regular expression for each of the regular sets described
below.
- All strings of lower-case letters that either begin or end in an
a. Some example strings in the language: a,
accc, abax, abaxa. Note: You may make a
regular definition for lower-case letters.
- All strings of a's and b's that contain no
three consecutive b's. Some example strings in the language: abab, abbaaa, eps (the empty string), baabb.
Problem 2
Use the subset construction to create a DFA that is equivalent to the following
NFA that uses the alphabet {a,b}. Show your work. Note: eps
denotes the empty string. *'d states are final states.
a b eps
--------------------
1 |{2,3} {1} {}
2 |{3} {3,4} {4}
*3 |{4} {} {}
*4 |{2,3} {1} {3}
Problem 3
Consider the following regular expression from the alphabet {a,b}:
b*a | bb
part A. Use Thompson's construction to make an NFA from the regular
expression (show it as a state diagram). NOTE: do not build an ad-hoc NFA:
the point is to use Thompson's construction.
part B. Use subset construction to create a DFA equivalent
to the NFA you gave for part A. Show your work. Show it as a state
table, using the sets from the NFA as the names for the new
states, as we did in examples in lecture.
Also show it as a state diagram, using capital letters as the state
names. Call the start state L, the next one M, etc. (to avoid
confusion with the alphabet used in the DFA). Show the correspondence
between the letters, L, M, etc. and the sets of states used in the
table. Do some hand runs of strings through the state diagram to
verify for yourself that it recognizes the language described by the
original regular expression (you don't have to write anything for this
last bit). I.e., this is a way to check that your answer to this
problem is correct.
The University of Southern California does not screen or control the content on this website and thus does not guarantee the accuracy, integrity, or quality of such content. All content on this website is provided by and is the sole responsibility of the person from which such content originated, and such content does not necessarily reflect the opinions of the University administration or the Board of Trustees