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: About this document
CSE 322
Assignment 10 Solution Set
Friday, March 8, 1996
-
(Thanks to P. Kromann for the trick on this one)
A DPDA for the given language:
The computation of abbac:

-
where
,
,
,
and the function
consists of only these rules:

-
Here's a Turing machine that accepts
:
Here's a brief description of all the states:
-
: Read the first blank.
-
: This is the start of the match loop. It looks for an a
or a b. If it sees a c, then we're done matching the first string.
-
: We've read a b and we're looking for the c.
-
: We've read an a and we're looking for the c.
-
: we're trying to match the b.
-
: we're trying to match the a.
-
: Scan left for the c.
-
: Scan left for the next thing to match in the first string.
-
: Verify that there is no other input in the second string.
-
: We've matched everything in the first string and found
nothing else in the second string, so accept the input.
Its computation of the input abcab:

-
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