Questions and Answers > California State University, San Marcos CS 421 Theory of computing CS421 - Krell – HW3C (based on Week 11 and week12a) -- PDA

Document Content and Description Below

California State University, San Marcos CS 421 Theory of computing CS421 - Krell – HW3C (based on Week 11 and week12a) -- PDA ================================================================= ... DUE: Week 12 Friday Nov 20, before midnight (11:55) TOTAL: 30 pts ?**? Name: =================================================================== ------------------------------------------------------- PDA Problem [2pts per problem = 26 pts] ---------------------------------------------------------- 1) The language is { (a | b)^n c (a | b)^n | n>=1 } abab c baba aaaa c bbbb Note that the left side and the right side of c need not be identical. But the lengths of the left and the right side must be the same. Start in q0 with Z on the stack. (assumed) a) Idea: Stay in q0 up to c, pushing X for a and b as they are read. Give the 4 Trs's here for all such valid cases: b) Idea: If c is seen switch to q1. No change to the stack. Give the Trs here (hint? What is on the stack?): c) Idea: In q1, as a's and b's are read, pop off X's. Give the 2 Trs's here for all such valid cases: The above Trs’s are not enough. We can finish in two different ways as you see below. 2) For the partial PDA you have designed above, finish it as a PDA-FS. d) For PDA-FS: what should you do if you see Z on the top of the stack in q1? (Hint: this means you have popped off all X’s) e) Give the Trs to do this. Note that you do not read any input. f) Under what circumstance does this PDA-FS stop and accept? Describe in English. g) Try the PDA-FS on abcaaa Give the state and the stack for each char read until the PDA stops and REJECTS the input. Read Char è new State new Stack content 3) For the partial PDA you have designed above, finish it as a PDA-ES. i) For PDA-ES: what should you do if you see Z on the top of the stack in q1? (Hint: this means you have popped off all X’s). j) Give the Trs to do this. Note that you do not read any input. k) Under what circumstance does this PDA-ES stop and accept? Describe in English. l) Try the PDA on abcaaa Give the state and the top of stack for each char read until the PDA stops and REJECTS the input. Read Char è new State new Stack content m) Is this PDA-ES deterministic? ------------------------------------------------------- Language Set Questions [4 pts] ------------------------------------------------------- 1.For every PDA, there is a DPDA. E.g. every PDA can be converted into a DPDA TRUE or FALSE? 2. For every DPDA accepting by empty stack, there is a DPDA accepting by final state. i.e. preserves determinism when you move to the final state design TRUE or FALSE? 3. For every DPDA accepting by final state, there is a DPDA accepting by empty stack. i.e. preserves determinism when you move to the empty stack design TRUE or FALSE? 4. Both a PDA and LL(1) parser can be constructed from a CFG. They are similar. But what is the main difference between them that makes LL(1) always deterministic? [Show More]

Last updated: 1 year ago

Preview 1 out of 3 pages