CPSC 313 Spring 2017 Page 1 of 16 CPSC 313 Spring 2017 University of Calgary Faculty of Science Final Exam June 2017 Time available: 180 minutes. No books or calculators are permitted. One sheet of notes (double sided) is permitted. The notes must be typeset in font size at least 11. Write answers in this booklet only. Do not open the exam until you are told to do so. Name: CPSC 313 Spring 2017 Page 2 of 16 1) Don’t panic! Partial credit is available. 2) Please give succinct, unambiguous, and well-phrased answers to the problems on the exam. These qualities will be taken into account in the assessment. 3) There are 46 points in total. Full answer is 40 points. 4) Please read the entire exam before writing anything. Please ask for clarification if any question is unclear. 5) Please note that points may be deducted for unintelligible handwriting. 6) You may use the blank pages at the end of the exam if you need more space for your answers. Please indicate clearly when your answers are continued on these pages. 7) For your convenience, the last page contains a collection of information. 8) Good luck! Problem Possible score Score 1 3 2 3 3 6 4 7 5 3 6 4 7 4 8 8 9 4 10 4 CPSC 313 Spring 2017 Page 3 of 16 Problem 1 Yes/No (3 points, 0.6 points each). Answer Yes or No. Let M be a standard Turing machine (with a single one-track tape and a single head) that decides the language {0n1n|n ≥ 0}. Which of the following must be true? No justification required. Question Yes No 1 M does not halt on input 11. 2 If M accepts a string w, it does so after at most O(|w|2) steps. 3 M never accepts before reading a blank. 4 For some input string, M changes at least one symbol on the tape. 5 For some input string, M moves its head to the left at least once. Problem 2 True/False (3 points, 0.6 points each). Answer True or False. The languages are over the alphabet Σ = {0, 1}. No justification required. Question True False 1 Every language L is infinite or decidable (or both). 2 For all languages L, if for every string x ∈ L there exists a DFA which accepts x, then L is regular. 3 If L is the union of two undecidable languages, then L is undecidable. 4 If L1 is decidable and L2 is context-free, then L1 ∩ L2 is decidable. 5 L is accepted by some DFA with 20 states if and only if L is accepted by some NFA with 20 states. CPSC 313 Spring 2017 Page 4 of 16 Problem 3 Short answer questions (6 points) 1) Give two context-free languages L1 and L2 such that L1 ∩ L2 = {aibicidiei|i ≥ 0}. Prove that the languages you give are context-free. 2) Give a regular expression for the language generated by the grammar S→ TT, T → aT|Ta|b. 3) Give a regular expression for the language consisting of all the strings in {0, 1}∗ that do not contain the substring 111. CPSC 313 Spring 2017 Page 5 of 16 4) Give an NFA with three states accepting the language L = {w ∈ a, b∗| w does not contain the substring aba} 5) Give a nonregular language L such that L∗ is regular. Briefly argue. 6) Give two languages A, B such that (A∗ ∩ B∗) 6= (A ∩ B)∗. Briefly argue. CPSC 313 Spring 2017 Page 6 of 16 Problem 4 Context-free grammars (7 points, 3.5 points each). Design a context-free grammar for each of the languages L1 and L2. You need to clearly explain how each grammar works. 1. In any string, a block is a maximal non-empty substring of identical symbols. For example, the string 0111000011001 has six blocks: three blocks of 0s of lengths 1, 4, and 2, and three blocks of 1s of lengths 3, 2, and 1. Let L1 be the set of all strings in {0, 1}∗ that contain two blocks of 0s of equal length. Thus, L1 contains the strings 01101111 and 01001011100010 but L1 does not contain the strings e, 000110011011, or 0000000111. CPSC 313 Spring 2017 Page 7 of 16 2. Let Σ = {0, 1} and Γ = {0, 1, #}. Let L2 = {x#y| x, y ∈ Σ∗ and x is a substring of yR}. Here uR denotes the reversal of the string u. For example, if u = 100 then uR = 001. CPSC 313 Spring 2017 Page 8 of 16 Problem 5 Non-regular language (3 points) Prove that the following language is not regular L = {0m1n|m, n ≥ 1 and m divides n}. CPSC 313 Spring 2017 Page 9 of 16 Problem 6 Decidable language (4 points). Prove that the following language is decidable. L = {〈M, w〉| M is a Turing machine and M only writes onto the cells initially occupied by w} CPSC 313 Spring 2017 Page 10 of 16 Problem 7 Undecidable language (4 points). Let M be a standard one-tape Turing machine, let w be an arbitrary input string, and let s be a positive integer. We say that M accepts w in space s if M accepts w after accessing at most the first s cells on the tape. Prove that the following language is undecidable. L = {〈M〉| M is a Turing machine and M accepts at least one string w in space |w|2.} CPSC 313 Spring 2017 Page 11 of 16 Problem 8 Language transformation (8 points). Let L ⊆ Σ∗ be an arbitrary regular language and let y ∈ Σ∗ be a fixed, given string. Prove that the language L−y = {uv| u ∈ Σ∗ and v ∈ Σ∗ and uyv ∈ L} is also regular. In other words, the language L−y consists of all the strings in L with the substring y deleted from them. For example, if L = {0, 10, 0102, 00010, 0102102} and y = 10, then L−y = {e, 02, 000, 02102, 01022}. If you construct one machine M′ = (Q′,Σ, δ′, q′0, F′) from another machine M = (Q,Σ, δ, q0, F), you must give precise definitions for Q′, δ′, q′0, and F′. You also need to briefly explain in English how your construction works. Hint: one approach is to run |y|+ 1 copies of the DFA for L. CPSC 313 Spring 2017 Page 12 of 16 (Blank page for continuing your answers to problem 8). CPSC 313 Spring 2017 Page 13 of 16 Problem 9 Dovetailing (4 points). Let Σ be an alphabet, and suppose that A, B ⊆ Σ∗ are recognizable languages for which both A ∩ B and A ∪ B are decidable. Prove that A is decidable. CPSC 313 Spring 2017 Page 14 of 16 Problem 10 Turing machine design (4 points). Show how to decide the language L = {0n1n| n ≥ 1} on a single-tape standard Turing machine in O(n log n) steps, where n represents the length of the input. (Note: Doing this in O(n2) steps is easy. Also, doing this in O(n) steps on a two-tape machine is also easy.) Alternatively, you can show how to decide the language L = {02k12k | k ≥ 0} on a single-tape standard Turing machine in O(k · 2k) steps, where 2k represents the length of the input. (For this problem, partial credit will only be given for substantial progress). CPSC 313 Spring 2017 Page 15 of 16 (Blank page for continuing your answers to any problem). CPSC 313 Spring 2017 Page 16 of 16 Theorem 1. Let L1 and L2 be regular languages over the alphabet Σ. Then the following languages are regular. 1. L1 = {w ∈ Σ∗| w /∈ L1}, 2. L1 ∪ L2, 3. L1 ∩ L2, 4. L∗1 , 5. L1L2, 6. LR1 = {w ∈ Σ∗| wR ∈ L1}. Theorem 2. Any finite language is regular. Theorem 3. Let L1 = {w ∈ {0, 1}∗| w = wR} and L2 = {0n1n| n ≥ 0}. Then L1 and L2 are not regular. Theorem 4. The language HALT = {〈M, w〉| M is a Turing machine and M halts on w} is undecidable. Theorem 5. The language HALT = {〈M, w〉| M is a Turing machine and M does not halt on w} is not recog- nizable. The Turing machine model A Turing machine M = (Q,Σ, Γ, δ, q0, qaccept, qreject) computes as follows. Initially, M receives its input w = w1w2 . . . wn ∈ Σ∗ on the leftmost n squares of the tape, and the rest of the tape is blank (i.e., filled with blank symbols). The head starts on the first character of the input. Note that Σ does not contain the blank symbol, so the first blank appearing on the tape marks the end of the input. Once M has started, the computation proceeds according to the rules described by the transition function δ. If M ever tries to move its head to the left off the left-hand end of the tape, the head stays in the same place for that move, even though the transition function indicates L. The computation continues until it enters either the accept or reject states, at which point it halts. If neither occurs, M goes on forever. Thus, a Turing machine M can fail to accept an input by entering the qreject state and rejecting, or by looping. Definition 6. A Turing machine M recognizes a language L if M accepts exactly those strings in L. A Turing machine M decides a language L if M accepts all strings in L and rejects all strings not in L. Example of a reduction Theorem 7. The language REV = {〈M〉| M is a Turing machine and M accepts wR whenever it accepts w} is undecidable. Proof. We reduce HALT to REV. Given any input 〈M, w〉 to the HALT problem, we construct the ma- chine M′ that, on any input y works as follows. 1. if y = 01, accept. 2. if y 6= 10, reject. 3. if y = 10, simulate M on w and accept if M halts. (We note that, when we construct M′, we have access to M and w; in other words, M and w are hard- coded into the states of M′). If M halts on w, then L(M′) = {01, 10}, so 〈M′〉 ∈ REV. Conversely, if 〈M, w〉 /∈ HALT, then L(M′) = {01}, so 〈M′〉 /∈ REV. This shows that the mapping f (〈M, w〉) = 〈M′〉 is a reduction from HALT to REV. Since HALT is undecidable, we conclude that the language REV is also undecidable.
欢迎咨询51作业君
