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: About this document
CSE 322
Assignment 10
Due Friday, March 8, 1996
-
Construct a DPDA which accepts the language
has an
equal number of a's and b's
. Run your machine on the
input abba.
-
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
-
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.
-
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