课程名称︰自动机与形式语言 课程性质︰必修 课程教师︰林智仁 开课学院：电机资讯学院 开课系所︰资讯工程学系 考试日期（年月日）︰108.1.7 考试时限（分钟）：160 试题 : Introduction to the Theory of Computation Final Exam January 7, 2019 10:20-13:00 ● Please write your answers in English. ● Please give details of your answers. A direct answer without explanation is not ciunted. ● Read the problem statements carefully. ● During the exam, you are not allowed to borrow others' notes. ● The problems may not be ordered according to difficulty. Try to work on easier problems first. Problem 1 (20 pts). Consider f(n) = e^(-n), g(n) = sin n + 2. (a) (10 pts) Use the definition of Small-O check whether f(n) = o(g(n)) or not. Do NOT directly calculate the kimit. That is, you need to consider/apply the definition of limit. (b) (10 pts) Use the definition of Big-O to check whether f(n) = O(g(n)) or not. Problem 2 (10 pts). Suppose f(n) = 2^O(n^3). Is f(n)^3 = 2^O(n^3)? Please provide detailed explanation. Problem 3 (20 pts). Consider the language {w#w | w∈{0,1}* }. (a) (15 pts) Design a 2-tape TM with no more than 6 states (including q_reject) to recognize the language. Note to simplify the figure, you don't need to draw q_reject and the transitions going to it. The strategy should be to ● copy first w to the second tape ● move head of the second the to the begining ● compare contents in the two tapes We require thae Γ = {0, 1, #, ∪}. Note that ● For the two-tape TM, we have δ: Q×Γ^2 → Q×Γ^2×{L,R,S}^2 ● There is no ∪ before the input (b) (5 pts) Simulate 01#01 by using machine obtained in (a) and the standard TM in Example 3.9 of textbook. Compare the number of stepd needed by the two machines. You need to show every step of the simulation. Problem 4 (20 pts). Consider the language {ww^R | w∈{0,1}*}, where w^R is the reverse of w. (a) (15 pts) Give a two-tape non-deterministic TM with no more than 5 states (including q_reject) to recognize this language. Note that here we allow S (stay moves) to make the problem easier. (b) (5 pts) Simulate the path (not the entire tree) that leads to the acceptance of 0110. Problem 5 (30 pts). A CNF <V,Σ,R,S> satisfies that R contains only the following types of rules. Type-V: A→BC Type-T: A→a Type-E: S→ε when a a∈Σ, A,B,C∈V, and B,C ≠ S. Let I_CNF = {<G> | G is a CNF and |L(G)| = ∞} be the set of CNFs that generates an infinite number of strings, where |L(G)| is the number of strings in the language L(G) of G. Various ways may be possible to prove that I_CNF is decidable, but wr would like you to answer the following sub-problems for a step-by-step proof. (a) (5 pts) Consider a CNF G = <V,Σ,R,S>, If now we consider only type-V rules, then the partial parse trees(not involving type-T and type-E rules) are binary trees where every node is a variable. For example, let G_a = <{S,A,B},{a},R,S>. where R contains the following rules. S→AB|ε A→BB|a B→AA An example of partial parse tree is shown below. S─B─A │ └A └A─B └B─A └A We say a partial pare tree generates a string w if it can be extended (with all rules in R) to a parse tree for w. For instance, the above partial tree can be extanded to the following parse tree generating aaaaaa. (Note that we say "if it can be." That is, a partial parse tree may not be able to generate any string; see sub-problem (b).) S─B─A ───a │ └A ───a └A─B ───a └B─A──a └A──a We define the height of a partial parse tree to be the maximum number of edges in paths starting from the root. Note that the height of the example in Figure 2 is 3. By the similar reasoning of pumping lemma, if some non-S variable appears at least twice in a path from root, then the looping part between the two occurrences can be repeated as many times as we want and therefore the partial parse tree can be extended to as large height as we want, and vice versa. For example, the partial parse tree shown above contains paths S-A-B-A where A appears twice, and indeed <G_a>∈I_CNF. ● Show that any partial parse tree contains an odd number of nodes. ● For any given CNF <V,Σ,R,S>, find an odd value z so that for any of its partial parse tree, if #nodes >= z, then some non-S variable must appear at least twice in a path from the root of the partial parse tree. Hint: You may directly use the fact that if the height of a bonary tree is no more than h, then #nodes <= 2^(h+1) - 1. (b) (5 pts) We are about to argue that partial parse trees generate long strings if the height is large, but there is one subtle issue that needs considerayion. Consider G_b = <{S,A,B},{b},R,S>. where R contains the following rules. S→AB|b A→AA B→b G_b can have a partial parse tree of height as large as we want (by repeatedly applying the rule A→AA), but L(G_b) = {b}! This is because A is non-deriving. i.e. A cannot derive any string of literals. For example, the following partial parse tree cannot generate any string. S─B └A─A └A Therefore we would like to remove all the non-deriving variables before our argument. Assume we already have a decider D for E_CNF = {<G>|G is a CNF and L(G)=Ø}. Use D to design an algorithm that finds out all non-deriving variabls of a given CNF. (c) (5 pts) Given a CNF G, we can apply the algorithm in (b) to find out all the non-deriving variables, remove them fome V, and remove all the rules involving any of them, getting a new CNF G'. It's clear that L(G) = L(G'). Because obtaining G' from G is a decidable procedure, we can now assume that the CNF G considered has no non-deriving variable. Show that for a CNF without non-deriving variables, any partial parse tree of height h > 0 cna generate at least one string, and that the strings w it generates satisfy |w| >= h+1. (d) (10 pts) Wrapping up our previous results, given a CNF G without non-deriving variable (by (b)), if there are enough nodes in any partial parse tree of G, by (a) the partial parse tree can be extended to as large height as we want, and therefore by (c) it can generate strings as long as we want. Use the above properties to derive an algorithm that decudes I_CNF. (e) (5 pts) Run your algorithm in (d) on <G_a> in (a) and <G_b> in (b). You don't need to provide details of running the algorithm in (b). -- 在很久的以後 你是否记得我 --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 1.163.101.65 ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/NTU-Exam/M.1547382138.A.D76.html