CSE 355 Final Exam (70 minutes) Name: Student ID: Please follow the submission guidelines when working on the exam: The exam is 70 minutes You must write the exam paper that has your name and student number preprinted on it. No notes, no books, no electronics, but two A4/letter cheat sheet is allowed. Individual effort: no shoulder-surfing. Raise your hand if you have a question and wait for us to come to you. During the exam, do not converse with other students. If you need to use the restroom, please raise your hand and let us know. Only one person is allowed to leave the room at a time. # 1 2 3 4 5 Total Points 20 20 20 20 20 100 Score 1 CSE 355 Intro Theoretical Computer Science, Fall 2021 Final Exam (70 minutes) 1. (20 points) Short Answer Questions I. Determine whether the following statement is true or false 1. (2 points) To show that a language is regular, one can (a) give a DFA that recognizes the language. True ? False ? (b) give an NFA that recognizes the language. True ? False ? (c) give a regular expression that describes the language. True ? False ? (d) use the pumping lemma for regular languages. True ? False ? (e) use closure properties. True ? False ? 2. (2 points) To show that a language L is NOT regular, one can (a) show that the language is context-free. True ? False ? (b) use closure properties. True ? False ? (c) use the pumping lemma for regular languages. True ? False ? (d) show that the language is finite. True ? False ? (e) show that L ? is not regular. True ? False ? 3. (2 points) To show that a language is context-free, one can (a) show that the language is not regular. True ? False ? (b) give a PDA that recognizes the language. True ? False ? (c) give a CFG that generates the language. True ? False ? (d) use the pumping lemma for CFLs. True ? False ? (e) use closure properties. True ? False ? 4. (2 points) To show that a language L is NOT context-free, one can (a) show that the language is regular. True ? False ? (b) use the pumping lemma for CFLs. True ? False ? (c) show that L ? is not a CFL True ? False ? (d) show that the language is the intersection of two CFLs. True ? False ? (e) show that the union of L with some regular language is not a CFL. True ? False ? 5. (2 points) To show that a language is decidable, one could (a) show that the language can be enumerated by a Turing machine. True ? False ? (b) show that the language is well-defined. True ? False ? (c) use closure properties. True ? False ? (d) describe a Turing machine for it and show it always halts. True ? False ? (e) write a program in C++ for it, show that the program always halts, and use the Church-Turing thesis. True ? False ? 2 CSE 355 Intro Theoretical Computer Science, Fall 2021 Final Exam (70 minutes) 6. (2 points) To show that a language is NOT decidable, one could (a) reduce an undecidable language to it. True ? False ? (b) show that it is not recognizable True ? False ? (c) use the Church-Turing thesis. True ? False ? (d) reduce it to an undecidable language. True ? False ? (e) ask 1000 people to write a program for it and find out that none of them can. True ? False ? 7. (2 points) The halting problem is undecidable. This implies that (a) there is no algorithm to decide whether a given program P terminates on input w when P and w are both provided as input

True ? False ? (b) for every program P and every input w, there is no algorithm to decide whether P terminates on input w. True ? False ? (c) Turing machines are not as powerful as programs in Java. True ? False ? (d) there is no algorithm to decide whether a given program P that implements a finite automaton terminates on input w when P and w are both provided as input

True ? False ? (e) there is an algorithm to decide whether a given program P that implements a finite automaton terminates on input w when P and w are both provided as input

True ? False ? 3 CSE 355 Intro Theoretical Computer Science, Fall 2021 Final Exam (70 minutes) II. Multiple choice questions: Circle all the correct answers. 8. (2 points) We have been assigned the task of selecting an interface language for a device controller. Two proposals have been made. Method C uses C++ while Method R uses regular expressions. Based on your knowledge of CSE 355, a primary benefit of Method C over Method R is (a) Method C can compute everything that Method R can, and more. (b) There is an algorithm to analyze Method C to detect infinite loops, but no algorithm for method R. (c) Method C can be represented as a Finite Automaton while Method R cannot. (d) Method C always terminates in fewer computation steps than Method R on the same input. 9. (2 points) We have been assigned the task of selecting an interface language for a device controller. Two proposals have been made. Method C uses C++ while Method R uses regular expressions. Based on your knowledge of CSE 355, a primary benefit of Method R over Method C is (a) There is an algorithm to detect dead code in Method R, but need not be an algorithm for Method C. (b) Method R can compute everything that Method C can, and more. (c) Method R is computationally equivalent to a Turing machine while Method C is not. (d) Method R can model a Finite Automaton while Method C cannot. 10. (2 points) We have been assigned the task of developing a software testing tool (tester) that can assess reachability of statements in a program. Namely, given a program and a statement x in the program (line in the code), the tester should produce a sequence of inputs that demonstrates that the program can reach statement x, or declare that statement x is not reachable under any input sequence. What should we respond to the manager who assigned this task? (a) There is no algorithm to decide whether this can be done or not. (b) This can be done when the program is in C++ but not always for other programming languages. (c) This can never be done because of the Church-Turing thesis. (d) This can always be done because of the Church-Turing thesis. 4 CSE 355 Intro Theoretical Computer Science, Fall 2021 Final Exam (70 minutes) 2. (20 points) Regular Languages (a) (5 points) Draw a DFA M1 for L1 = {w | w contains 011 as a substring} (b) (5 points) Provide a regular expression for L1 (c) (5 points) Draw a DFA M2 for L2 = {w ? {0, 1} ? |w is a binary representation of an integer that is a multiple of 3} (d) (5 points) Draw an NFA for L1 ? L2: 5 CSE 355 Intro Theoretical Computer Science, Fall 2021 Final Exam (70 minutes) 3. (20 points, 5 per part) Context-free Languages For each language, do the following: (a) Indicate the language of the following context-free grammar: S ? aaT bb T ? aT b|a (b) Indicate the language of the following context-free grammar: S ? aSb | aRb R ? aaRb | aab (c) Give context-free grammar generating the language {w | w = w R, w is a palindrome but not start with b} (d) Draw push down automaton for language of strings which the number of 0s is not equal to the number of 1s. (S = {0, 1}) 6 CSE 355 Intro Theoretical Computer Science, Fall 2021 Final Exam (70 minutes) 4. (20 points) Turing Machine CLEARLY MARK HERE ONE PROBLEM you want us to grade: (a) ? (b) ? (a) Draw a state diagram for Turing machine that decides the language L = {w ? {a, b} * | the number of as is equal to the number of bs in w}. E.g. abaabb (b) Draw a state diagram for Turing machine that decides the language L = {a n b mc n+m | n, m = 0}. Note: The empty string is a valid string of this language. 7 CSE 355 Intro Theoretical Computer Science, Fall 2021 Final Exam (70 minutes) 5. (20 points) Decidability Show that { | A is a DFA that doesnt accept any string containing an even number of 0s} is decidable. 8 CSE 355 Intro Theoretical Computer Science, Fall 2021 Final Exam (70 minutes) ROUGH WORK ONLY (not graded) 9 CSE 355 Intro Theoretical Computer Science, Fall 2021 Final Exam (70 minutes) ROUGH WORK ONLY (not graded) 10

Attachments:

cse-355-f-21-....pdf