課程名稱︰計算理論 課程性質︰選修 課程教師︰顏嗣鈞 開課學院：電資學院 開課系所︰電機系 考試日期（年月日）︰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)