COMS 331: Theory of Computing, Summer 2022 Exam 1

 June 2 (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 8 points). Problem types are very similar to homework problems. • The exam topics cover anything about Regular languages, which is all the materials covered before the exam. • The exam opens 00:01 am to 11:59 pm June 2. But Instructors will only be able to answer questions from 10 am to 10 pm June 2 (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 2 • To ensure you have the full 100 minutes for your exam, start no later than 10:19 pm, June 2. All answers should be explained. Some definitions: For DFAs, δ : Q × Σ → Q, δ(q, a) = r. δˆ:Q×Σ∗ →Q,δˆ(q,ε)=q,δˆ(q,xa)=δ(δˆ(q,x),a)∀x∈Σ∗,a∈Σ For NFAs, δ : Q × Σ → 2Q, δ(q, a) = T, T ⊆ Q. δˆ:2Q×Σ∗→2Q,δˆ(A,ε)=A,δˆ(A,xa)= �� δ(q,a)∀x∈Σ∗,A⊆Q,a∈Σ q∈δˆ(A,x) Pumping Lemma: If L is regular, then ∃k ∈ N, such that ∀w ∈ L with |w| ≥ k, ∃x, y, z such that w=xyz,y̸=ε,|xy|≤k,∀i∈N xyiz∈L. 1 Problem 1 (extra 2 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). Prove the language L is regular. Problem 3 (35 points). Prove some closure property of Regular languages. (Hint: You can make use of closure properties proved in lectures) Problem 4 (30 points). Prove a language L is NOT regular. Problem 5 (extra 8 points). Prove or Disprove: 2