CSE396                    Problem Set 9 Answer Key                 Spring 2010


(1) The DFA for the complement of a*b*c* has states P -> aP | bQ | cR, 
Q --> bN | bQ | cR, R --> cR | aN | bN, and N --> aN | bN | epsilon.
Here "N" is the "nirvana" state of the complemented DFA.  (When you have
a regular grammar, there is no essential difference between "state"
and "grammar symbol".)


(2) (a) Given E = {a^n b^n c^n : n >= 0} = {a^i b^j c^k : i=j && j = k}:
Define G by S --> P  |  ... where P is the variable from (1) for the complement
of a*b*c*.  For the "..." we want to get E' = {a^i b^j c^k : i != j OR j != k}.
Now E' equals the union of these four languages:

E1 = {a^i b^j : i > j} . c*
E2 = {a^i b^j : i < j} . c*
E3 = a* . {b^j c^k : j < k}
E4 = a* . {b^j c^k : j > k}

where in all cases i,j,k can be zero.  Allocate start variables S1,S2,S3,S4 for
the "set" parts of the respective languages, and variables A,B,C generating 
zero-or-more a's, b's, c's respectively.  Then in full we have:

S  -->  P  |  S1 C  |  S2 C  |  A S3  |  A S4
P  -->  (as above)
A  -->  aA | epsilon,  B --> bB | epsilon,  C --> cC | epsilon
S1 -->  a S1 b  |  aA
S2 -->  a S2 b  |  bB
S3 -->  b S3 c  |  bB
S4 -->  b S4 c  |  cC

Note the extra a,b,b,c in the final productions, to make sure of getting
strict inequality.

(b) E = {a^n b^n}.c* intersect a*.{b^n c^n}.  A DPDA M accepting {a^n b^n}.c*
pushes an A for each a read, then pops an A for each b read.  If the stack is
empty upon reading the first c or blank, M accepts iff the rest of the input
tape has no 'a' or 'b'.  If any character is not in a*b*c* order, M rejects.
A DFA M' for the second conjunct skips over any leading a's, and pushes B for
each 'b', then pops for each 'c' read, and accepts iff the blank at the end of
the input comes exactly when the stack tape is empty.


(3) To prove A = {w c^m w^R : w \in {a,b}*, m = |w|} is not a CFL:
Let any n > 0 be given.  Take x = a^n b^n c^{2n} b^n a^n.  Then x is in A.
Let any breakdown x =: yuvwz with |uvw| <= n, u,w not both empty, be given.
For the uvw portion, we have the following cases:

(i) uw contains a 'c'.  Then uvw cannot touch both the a^n b^n part at the left
and the b^n a^n part at the right.  Hence pumping down creates an imbalance with
either the left or the right side---between the length of the c's part and it.
(Pumping down means leaving the string x^{(0)} = yu^0vw^0z = yvz.)

(ii) uw contains no 'c'.  Then it can only intersect the left-hand side or the
right-hand side.  Since |uw| > 0, pumping down will shorten one side relative
to the other.  Hence the right-hand side's a's and b's will no longer be the
reverse of those on the left-hand side.


(4) (a) A DTM M can use the strategy of matching chracaters from the ends, and
making sure that any chars left over in the middle are just c's.  Then it has to
check that the length of the c's part equals the length of the X-ed out chars
to its left (or to its right---those will already have been verified as equal).
Optionally, the first pass can check that the input matches the regular
expression (a+b)*c*(a+b)*.  This doesn't help with either the "w ... w^R"
part or the "|w| = m" part, but it does allow one to say subsequently that
M maintains the tape invariant

    Tape \in X*(a+b)*c*(a+b)*X*

with Xed-out characters matching from the ends, in the sense of a palindrome.
With all this said, the arc-node details are similar to the examples given in
lecture.  See the separate file "CSE396ps9keyTM.pdf" off the course page.

(b) As with those examples for 1-tape machines, the backing-and-forthing takes
quadratic time.  A 2-tape DTM can decide whether x is in A in linear time
as follows:

Stage I:   Copy the input string x in reverse onto Tape 2. 
           Accept if it is empty. 
Stage II:  Then compare the tapes in a pass---if they don't match, reject.
Stage III: If they do match, blank out the second tape, ending with heads
           at left.
Stage IV:  Then march the Tape 1 head to the first 'c'.  If there isn't any,
           reject (since the empty string already got accepted in Stage I).
Stage V:   Copy c's to Tape 2 until reading an 'a' or 'b'---if there is none,
           or if there are any c's further down the input tape, reject.
Stage VI:  Finally rewind the heads and check that the number of c's on Tape 2
           equals the length of the first block of a's and b's before it
           on Tape 1.  If so, accept x; if not, reject.

As described it's 6 or 7 passes (depending on whether you rewind first and
then compare in stage VI, or count while rewinding), so it's O(n) time.