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



next up previous
Next: About this document

CSE 322 Assignment 10 Solution Set Friday, March 8, 1996

  1. (Thanks to P. Kromann for the trick on this one) A DPDA for the given language:

    The computation of abbac:

  2. where , , , and the function consists of only these rules:

  3. Here's a Turing machine that accepts :

    Here's a brief description of all the states:

    Its computation of the input abcab:

  4. Let . Assume all the productions in P, not of the form , are numbered 1 to m.

    The PDA will accept the language generated by G. We need to specify Q and .

    The function consists of the following rules:





James Fix
Tue Mar 12 08:07:49 PST 1996