CSE 105 Homework 5
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
CSE 105
Homework 5
Due: Friday November 04, 2022
Instructions
Homework should be done in groups of one to three people. You are free to change group members at any time throughout the quarter. Problems should be solved together, not divided up between partners. A single representative of your group should submit your work through Gradescope. Submissions must be received by 11:59pm on the due date, and there are no exceptions to this rule.
Homework solutions should be neatly written or typed and turned in through Gradescope by 11:59pm on the due date. No late homeworks will be accepted for any reason. You will be able to look at your scanned work before submitting it. Please ensure that your submission is legible (neatly written and not too faint) or your homework may not be graded. A typed PDF submission is recommended.
You may consult your textbook, class notes, lecture slides, instructors, TAs, and tutors for help with homework. You should not look for answers to homework problems in other texts or sources, including the internet. Only post about graded homework questions on Piazza if you suspect a typo in the assignment, or if you don’t understand what the question is asking you to do. Other questions are best addressed in office hours.
Your assignments in this class will be evaluated not only on the correctness of your answers, but on your ability to present your ideas clearly and logically. You should always explain how you arrived at your conclusions, using mathematically sound reasoning. Whether you use formal proof techniques or write a more informal argument for why something is true, your answers should always be well-supported. Your goal should be to convince the reader that your results and methods are sound.
Reading Sipser Section 2.1, 2.2, examples from 2.3, 3.1.
Key Concepts Pushdown automata, context-free languages, Turing machines.
1. (15 points) Consider the PDA, M, determined by the following state diagram.
(a) Give a string of length 5 that is accepted by M . Explain why it is accepted by tracing through the computation of M on this string.
(b) Give a string of length 5 that is not accepted by M . Explain why it is not accepted by tracing through the computation of M on this string.
(c) Is the language of M finite or infinite? Explain your answer, making specific reference to the states in the diagram.
2. (10 points) Let A be the following language over the alphabet {0, 1} A = {1n 0n+m1m | n,m ≥ 0}
In JFLAP, draw the state diagram of a PDA M such that M recognizes A and M has at most eight states. Along with the JFLAP diagram, include a brief description (in English) of why each state is included and why you chose to make each state either accepting or non-accepting.
3. (10 points) Fix an arbitrary alphabet Σ . Prove that the class of context-free languages over Σ is closed under concatenation in below fashion:
Prove that, for any languages L1 ,L2 over Σ, if there are CFGs G1 and G2 such that L1 = L(G1 ) and L2 = L(G2 ), then there is a CFG that generates L1 · L2 . Prove your answer with an example.
4. (15 points) Consider the Turing machine, M, determined by the following state diagram.
(a) Give a string of length 3 that is accepted by M . Explain why it is accepted by tracing through the
computation of M on this string.
(b) Is M a decider? Prove your answer.
(c) Prove that the language of M is context-free.
2022-11-06