COMS 331: Theory of Computing, Summer 2022 Exam 2 June 16 (Thursday) on Gradescope. •

 This is a closed-book, closed-note exam. • The exam contains 3 problems(worth 100 points) and an extra credit problem(worth 10 points). Problem types are very similar to homework problems. • The exam topics cover anything about Context-free languages. • The exam opens 00:01 am to 11:59 pm June 16. But Instructors will only be able to answer questions from 10 am to 10 pm June 16 (Ames local time) on Piazza. • Make a private post on Piazza if you have questions. • You have 100 minutes to finish and submit your solutions on Gradescope. • Once you open the exam, the 100-minute window starts counting. Make sure you are ready to take the exam when you click it. • You have to submit your solution by the earliest time of your 100 minutes window or 11:59 pm, June 16 • To ensure you have the full 100 minutes for your exam, start no later than 10:19 pm, June 16. All answers should be explained. Some definitions: Pumping Lemma of context-free languages: If L is context-free, then ∃k ∈ N, such that ∀w ∈ L with |w| ≥ k, ∃u,v,x,y,z such that w = uvxyz,vy ̸= ε,|vxy| ≤ k, ∀ i ∈ N uvixyiz ∈ L. 1 Problem 1 (extra 5 points). Write the following statement and sign. Otherwise, your exam will not be graded. I pledge my honor that I did not receive any unauthorized help during the exam. Problem 2 (35 points). Give a context-free grammar that generates the language L. Problem 3 (35 points). Give the state diagram of a NPDA that accepts the language L Problem 4 (30 points). Prove a language L is NOT context-free. Problem 5 (extra 10 points). Prove or Disprove: 2