课程名称︰ 自动机与形式语言 课程性质︰ 资工系必修 课程教师︰ 林智仁 开课学院： 电机资讯学院 开课系所︰ 资讯工程学系 考试日期（年月日）︰ 2008/12/4 考试时限（分钟）： 90 是否需发放奖励金： 是 （如未明确表示，则不予发放） 试题 : 1.(a) (12%) In using the pumping lemma, we use a property that not(A and B and C) (1) is equivalent to B and C → not A, (2) where A, B, and C are any statements. Use a (detailed) truth table to prove the above property (i.e., prove (1) is equivalent to (2). Please consider all 8 combinations of A, B, C; don't put "B and C" as a variable). (b) (13%) In almost all Pumping Lemma examples we discussed, we consider i ● A: xy z belongs to the language, for all i >= 0. ● B:│y│> 0 ● C:│xy│=< p and prove (2). Then from the above property that (1) and (2) are equivalent, we obtain the desired result (1). Assume that instead of (2) , we are now able to prove that B → not A. (3) Is (3) then sufficient to imply (1)? If your answer is yes, show your argument and give an example (i.e., give a language and in the use of pumping lemma you use (3)). If your answer is no, give your detailed argument. 2.(20%) Using pumping lemma to prove that the following language is not regular: r s {0 1 │ r >= 2s, r >= 0, s >= 0, r and s are integers}. We required you to directly use the standard pumping lemma. Don't use something else (eg. do complement of this language or union it with something else; and then prove blah blah). 3.(25%) Consider the following PDA with Σ = {0}: ┌─┐ 0,ε → 0 ┌─┐ 0,ε → ε ╔═╗ →│q0│ ─────→│q1│ ─────→ ║q2║ └─┘ └─┘ ╚═╝ Find CFG of this PDA's language. You are required to follow the same procedure in Lemma 2.27 to generate rules (Lemma 2.27 proves that if a PDA recognizes some language, then it is context free. Your notes should have provided enough materials regardless of whether you have the textbook or not.) 4.(20%) Assume Σ={0, 1}. We would like to design a (one-tape deterministic) Truing machine to shift a string. That is, if w is the input, after running the machine, we have Uw in the tape. Give the transition diagram as well as the formal definition of this TM. 5.(10%) Consider the following two-tape TM: U → R U → L 0 → R U → R ┌─┐ U → R ┌─┐ U → L ┌─┐ U → R ┌─┐ U → R ┌─┐ →│q0│ ────→│q1│────→│q2│────→│q4│ ────→│qa│ └─┘ └─┘ └─┘ └─┘ └─┘ 0 → R │↑ ↑│ │↑U → 0,R U → 0,R││ ││ ││0 → R └┘ U → L ││0 → R └┘ 0 → L ││0 → L ││ │↓ ┌─┐ │q3│ └─┘ Assume the initial configuration is U0000 in the first tape and UU... in the second tape. Run the TM and give the sequence of configurations. --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 61.229.226.87