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)