辅导案例-S 317
CptS 317: Automata and Formal Languages Final Exam (Take Home) Assigned: May 1, 10 AM Due by: May 4, 2 PM Instructions: 1. Make sure that your exam has 2 pages (including this cover page). The exam questions begin on the second page. 2. There are 10 questions in this exam; Questions Q2 and Q3 have multiple parts. The point each question carries is shown in parenthesis. The points add up to 100. Read each question carefully before you begin writing your solution. 3. The exam is take-home. Your solution in PDF format is to be submitted on OSBLE. You may either type-up your solution to produce a PDF document, or hand-write your solution and scan to get a PDF document. Both options are fine. If you hand-write, make sure to write legibly. 4. The exam is due Monday May 4, 2020 by 2 PM. 5. As a reminder, the same WSU Standards of Conduct for Students, particularly the section on Academic Integrity, apply to this take-home exam as any in-class exam. See the section on Academic Integrity in the syllabus of the course for further information. 1 1. (8 pts) Now that you have completed this course and experienced what it had to cover, suppose you were asked to develop a crisp and informative “course description” for it for use for future semesters. The course description is to consist of a brief paragraph (roughly 3 to 5 sentences) followed by a list of topics. What would your course description be? 2. (6 pts) Consider the 8 homeworks you have worked on this semester. For each homework, do the following two things: i) Write a sentence listing the topics the homework covered; and ii) Write a sentence describing something relevant to the course that you have learned from solving one of the problems, or from reflecting on the posted solutions. 3. (12 pts) Let L and M be two languages. The XOR operator ⊕ between two languages is defined as follows: L⊕M = {w|w is either in L or M but not in both } Is the XOR operation closed for the class of: a) regular languages? b) context free languages? Answer each part with a yes/no, followed by a brief justification. 4. (10 pts) Write a context free grammar generating the language {a2nb3ma2mbn : n > 0,m > 0}. Please check your solution by actually generating an example word from your grammar. 5. (10 pts) Show the language accepted by a pushdown automaton that never pops a stack is regular. 6. (10 pts) Provide an implementation level description of a Turing machine that accepts the language given by the regular expression a∗bb. 7. (14 pts) Say that a variable A in context free language G is usable if it appears in some derivation of some string w ∈ G. Given a CFG G and a variable A, consider the problem of testing whether A is usable. Formulate this problem as a language and show that it is decidable. 8. (10 pts) Let A be a language and ATM be the language ATM = {< M,w > |M is a Turing machine and M accepts w} Show that A is Turing recognizable if and only if A ≤m ATM. Recall that the notation ≤m denotes mapping reducible. 9. (12 pts) Provide an analysis of the time complexity of EQDFA and show that it is in P . Note that here, EQDFA is an algorithm which takes two DFAs as inputs, and determines whether they accept the same language. 10. (8 pts) Suppose you were invited to participate at an Oxford-style debate a student body at a major research university organized on the following topic: “Introduction to Theory of Computation” should be a required course for all Com- puter Science students seeking a Bachelors degree. Write a brief paragraph arguing for or against this debate question. You will be graded on this not for the side you pick, but rather for the quality of the argument you make (i.e., the points you make in your argument). 2