课程名称︰计算理论 课程性质︰选修 课程教师︰颜嗣钧 开课学院：电资学院 开课系所︰电机系 考试日期（年月日）︰2011/11/14 考试时限（分钟）：9:10 ~ 12:00 是否需发放奖励金：是 （如未明确表示，则不予发放） 试题 : Theory of Comutation Midterm Exam, Nov. 14,2011 1. (21 pts) Are the following statements true of false.Justify by a proof or a suitable counterexample. (a) If L_1 is finite and L_1 ∪ L_2 is regular then L_2 is regular. (b) If L_1 is regular (and infinite) and L_1 ． L_2 is regular then L_2 is regular. (c) If L^* is regular,so is L. (d) Consider a language L and a homomorphism h. If h(L) is regular ,then L is always regualr. (e) Let L_1 ⊆L_2 (over alphabet Σ) both be regular languages. If L_2 can be accepted by a DFA with n states ,then L_1 can always be accepted by some DFA with no more than n states. (f) (R∪S)^* =R^* ∪ S^* ,where R and S are two languages. (g) (R∩S)T=RT∩ST, where R,S and T are languages. 2. (4 pts) Give a regular expression for the language containing all strings of 0's and 1's such that every pair of adjacent 0's appears before any pair of adjacent 1's. (Fpr example,01001011011 is in the language,while 011001011 is not.) ─ ─ 3. (10 pts) A shuffle of two strings x,y∈Σ^* denoted by x||y is the set of strings that can be obtained by interleaving the strings x and y in any manner. For example ab||cd ＝{abcd,acbd,acdb,cabd,cadb,cdab}. (The strings need not be of the same length.) For two sets of strings A,B , the shuffle is defined as A||B＝∪_x∈A ,y∈B x||y. Prove that if both A and B are regular,then A||B is also regular. 4. (10 pts) Define L_1 # L_2 ＝{x#y | x∈L_1 ,y∈L_2 , |x|＝|y|},where # is a new symbol. Is the following statement true or false ? Justify your answer. ─If L_1 and L_2 are regular ,then L_1 # L_2 is also regular. 5. (10 pts) Use the pumping lemma to show that L＝{0^n l^m|n,m≧1 and m leaves a remainder of 3 when divided by n} is not regular.(For example,0^4 1^7, 0^5 1^13 are in L.) (Hint: Let p be the pumping constant.Take ω=0^p+4 1^p+7.) 6. (10 pts) Given a language L⊆Σ^* and two strings x,y∈Σ^* , x≡_L y iff ∀z∈Σ^* , xz∈L ⇔ yz∈L.Give the ≡_L equivalence classes of the language L＝a^*ba^*. Also draw a minimum DFA accepting L. 7. (10 pts) Let L be a language. Show that if every subset of L is regular, then L must be finite (i.e.,containing a finite number of strings). (Hint:Prove it by contradiction. Note that for every ω'∈ L such that |ω'| > 2|ω|).(|ω| denotes the length of ω.) Use the pumping lemme if needed.) 8. (10 pts) Consider the ε-NFA defined in Figure 1 (where → and * mark the initial and final states,respectively): ─────────────── │ │ ε │ a │ b │ c │ ─────────────── │→p │ Φ │{p} │{q} │{r} │ ─────────────── │q │{p} │{q} │{r} │Φ │ ─────────────── │*r │{q} │{r} │Φ │{p} │ ─────────────── Figure 1 : Anε-NFA (a) (4 pts) Compute the ε-closure of each state. (b) (6 pts) Convert the automaton to a DFA, 9. (15 pts) Consider the DFA given in Fingure 2.Suppose we want to find an equivalent minimum DFA. (a) (10 pts) Use the table filling method discussed in class to find all distinguishable pairs of states. Shoe T[i,j] for 1<＝ i < j <= 4. Mark T[i,j] with an ”X“ if there exists a string ω that can tell i and j apart as far as reaching a final state is concerned. Show your work in sufficient detail. (b) (5 pts) Draw the minimum DFA. ╭ ╮ b ╭╭ ╮╮ → 1 ←──────────── 2 ╰ ╯ ╰╰ ╯╯ │ │ ↑ ↑│ │ │b │ ││ │ │ a │ ││ │ │ ╭ ╮──── ││ │ ──────→ 3 ││ │ ╰ ╯ ││ │ │ ││ │ │ ││ │ │b a││a │ │ ││ │a │ ││ │ ↓ ││ ────────→ ╭ ╮────── │ 4 ←────── ╰ ╯ ↑│ ─ b Figure 2 : A DFA. ※ 编辑: nihility7893 来自: 140.112.25.106 (01/15 14:44)