PROBLEM SET 2, CSC 280, 2006
DUE BEFORE CLASS, WED. FEB. 8
The second problem set is as follows. All 10 problems will be marked out
of the same total. Answers to 7 questions, including questions 6 and 7,
make a complete answer paper. However, you can do all questions to
earn bonus points.
Keep your eyes on the instructor's and the TAs' web site for any corrections
or discussion.
PROBLEM 1
~~~~~~~~~
Show that if L is regular then so are the following (one straightforward
approach is to modify FAs):
a. the set of suffixes of L (a string y is a suffix of w if w = xy
for some string x)
b. The set of substrings of L (y is a substring of w if w = xyz for
some strings x, z)
c. the reverse of L, i.e., {w | w^R (the reverse of w) is in L}
Problem 2
~~~~~~~~~
a. The *prefix-free* part of a language L is defined (with e = the
empty string) as {w | w is in L, and if wx is in L then x = e}.
By considering the expression L-(L-{e})XX*, where X is the alphabet
of L, prove that the prefix-free part of any regular language is
regular. (Hint: the intention in assigning this problem is to
illustrate the usefulness of closure properties!)
b. Let {L1, L2, L3, ...} be an infinite class of regular languages,
where for i =/= j, Li is not a subset of Lj. Consider the infinite
union
L = (L1 U L2 U L3 U ...).
Give an example of such a class of languages for which L is regular,
and an example of such a class where L is not regular. Briefly
justify your example in each case.
PROBLEM 3
~~~~~~~~~
Prove the following indentities for regular expressions r, s, and t.
Here r = s means that L(r) = L(s). We use e for the empty-string symbol.
a. Ør = rØ = Ø
b. Ø* = e
c. e* = e
d. eu = ue = u
e. r(s U t) = (rs U rt)
f. (rs)*r = r(sr)*
PROBLEM 4
~~~~~~~~~
a. Construct a regular expression for the set of strings over {a,b}
of length >= 3 whose third and third-to-last symbols are both b.
b. Give the state diagram of an NFA for the set in (a), keeping the
number of states as small as you can manage.
PROBLEM 5
~~~~~~~~~
a. Show the state diagram of a NFA with a single accepting state,
recognizing L(((aa U bb)*ab) U b*).
b. Convert the NFA of part (a) to a (deterministic) FA by the method
covered in class (or Sipser). The resultant state diagram (with
unreachable states omitted, or not introduced in the first place)
should be no more complex than the original NFA -- which indicates
that the theoretically exponential growth in size implicit in using
the power set of the NFA's states need not always occur in practice.
c. Begin the process of converting the result of part (b) back to
a regular expression, using the method in the proof that every
regular language can be described by a regular expression. Go
as far as "ripping out" two states, one of which should be a state
with a self-loop; also combine edges wherever possible. You needn't
take this to the end, because the result would be unpleasantly
complex (both for you and the grader!)
PROBLEM 6
~~~~~~~~~
Use the pumping lemma (and perhaps closure properties) to show that
the following sets are not regular:
a. the set of "padded palindromes" over alphabet {0,1}:
{x^m w y^n | x,y in {0,1}, m,n >= 0, and w = w^R}
b. the set of strings over {a,b} where the number of a's is a perfect cube.
PROBLEM 7
~~~~~~~~~
Use the pumping lemma to show that the following sets are not regular:
a. the set of strings consisting of n 0s, where n is a power of 2;
b. {0^n| n is prime}; (Hint: Pump up a string till you get a multiple
of the original length.)
c. the set of initial segments of the infinite string
10110111011110111110...
(Hint: problem 1 is relevant.)
PROBLEM 8
~~~~~~~~~
The following grammar G formalizes a simple "morphological" CFG
used as an example in class:
G = ({N,A},{a,c,d,e,f,i,l,n,o,r,s,u},{N->clue, N->sound,
A->fair, A->sound, N->Aness, A->unA, A->Nless},N}.
Show that L(G) is regular, by
a. constructing the state diagram of an NFA that recognizes L(G); and
b. completing the proof by giving an inductive argument that your NFA
accepts a string iff the grammar derives it from N. (Hint: the
inductive hypothesis should probably make a connection between
derivability of strings from A and N and certain special states
in your NFA. Don't forget about either the "if" or "only if"
direction in your argument. Entirely separate inductive arguments
could be made in the 2 directions, but combining them is tidier.)
In doing this problem, do not use any theoretical results about
CFGs or (N)FAs, other than the basic definitions of these models
and the equivalence of NFAs with FAs.
PROBLEM 9
~~~~~~~~~
Informally show that the sentence grammar discussed in class
also generates a regular language:
G = ({S,NP,VP,V},{dogs,cats,noises,make,hear},{S->NP VP, NP->dogs,
NP->cats, NP->noises, VP->V NP, VP->V S, V->make,V->hear},S).
As an informal argument, describe the language L(G) generated by G
as clearly as you can in English (perhaps with some examples), and
show an NFA for recognizing that language, indicating in words why
it will generate the language L(G) as you previously described it.
PROBLEM 10
~~~~~~~~~~
Sipser 2.4 (b,c,e,f)