编译原理与实践第二章答案.doc

The exercises of Chapter Two2.1 Write regular expression for the following character sets, or give reasons why no regular expression can be written:a. All strings of lowercase letters that begin and end in a.Solutionaa-z*a | ab. All strings of lowercase letters that either begin or end in a ( or both)both:a(a|b|c|z)* ac. All strings of digits that contain no leading zerosSolution1-90-9*d. All strings of digits that represent even numbers(0|1|2|9)*(0|2|4|6|8)e. All strings of digits such that all the 2s occur before all the 9sSolutiona=(0|1|3|4|5|6|7|8)r=(2|a)*(9|a)or9*2*or9*2(1|3-8)*92*g. All strings of as and bs that contain an odd number of as or an odd number of bs(or both)Solutionr1=b*a(b|ab*a)*-odd number of asr2= a*b(a|ba*b)*-odd number of bsr1|r2|r1r2|r2r1orb*a(b*ab*a)*b*|a*b(a*ba*b)*a*i. All strings of as and bs that contain exactly as many as as bsSolutionNo regular expression can be written, as regular expression can not count.2.2 Write English descriptions for the languages generated by the following regular expressions:a. (a|b)*a(a|b|)SolutionAll the strings of as and bs that end with a, ab or aa.OrAll the strings of as and bs that do not end with bb.b. All words in the English alphabet of one or more letters, which start with one capital letter and dont contain any other capital letters.c. (aa|b)*(a|bb)*SolutionAll the strings of as and bs that can be divided into two sub-stings, where in the left substring, the even number of consecutive as are separated by bs while in the right substring, the even number of consecutive b are separated by as.d. All hexadecimal numbers of length one or more, using the numbers zero through nine and capital letters A through F, and they are denoted with a lower or uppercase “x” at the end of the number string.2.12 a. Use Thompsons construction to convert the regular expression (a|b)*a(a|b|) into an NFA.b. Convert the NFA of part (a) into a DFA using the subset construction.Solutiona. An NFA of the regular expression (a|b)*a(a|b|)babaa751234689171112131415161810b. The subsets constructed as follows: 7 = 7, 5,1,3,8,9 7 a = 2, 10 7 b= 42,10 = 2,6,5,1,3,8,9, 10,17,11,13,15,16,18baa12345aaabbbb2,10a = 2, 10, 122,10b =4, 142,10,12 = 2,6,5,1,3,8,9,12,18,10,17,11,13,15,162,10,12a = 2,10,122,10,12b = 4, 144,14 = 4,6,5,1,3,8,9,14,184,14a = 2,104,14b = 44 = 4,6,5,1,3,8,94a =2,104b =42.15rFigure 1 r*sFigure 2 s*Assume we have r* and s* according to figure 1 and 2:rsFigure 2 r*s*Consider r*s* as followThis accepts, for example, rsrs which is not in r*s*. I. e., in this case we cannot eliminate the concatenating transition.2.16 Apply the state minimization algorithm of section 2.4.4 to the following DFAs:cc12435aba. Solutiona. Step 1: Divide the state set into two subsets:1, 2, 34, 5 Step 2: Further divide the subset 1,2,3 into two new subsets:12, 3 Step 3: Can not divide the subsets any more, finally obtains three subsets:12, 34, 5Therefore, the minimized DFA is:cc12435abSolutionb. Step 1: Divide the state set into two subsets:1, 23, 4, 5 Step 2: Further divide the subset 1,2 into two new subsets:12 Step 2: Further divide the