Date: Wed, 08 Jan 1997 20:36:24 GMT Server: NCSA/1.4.2 Content-type: text/html CSE 322 Assignment 10 Due Friday, March 8, 1996



next up previous
Next: About this document

CSE 322 Assignment 10 Due Friday, March 8, 1996

  1. Construct a DPDA which accepts the language has an equal number of a's and b's. Run your machine on the input abba.
  2. Use the construction given in class of a PDA from a context-free grammar to construct a PDA which accepts the language generated by the grammar . Recall that the language generated by this grammar is the language of number 1 above. Run your machin on the input abba
  3. Construct a one-tape Turing machine which accept the language . Please use the Turing machine diagrams which are defined in Chapter 9. Describe in English what each of your states does, that is, describe the algorithm implemented by your Turing machine. Run your machine on the input abcab.
  4. Give a construction of the PDA from a context-free grammar where the PDA behaves like the bottom-up parsing method. You will need to ``shift'' input onto the stack and ``reduce'' according to the grammar productions. Each reduction will have to broken up into a number of steps governed by a set of states. Try to make your construction as brief and elegant as the top-down construction handed out.




James Fix
Sun Mar 3 12:20:28 PST 1996