[next] [prev] [prev-tail] [tail] [up]

 Exercises

  
3.1.1
For each of the following relations give a recursive finite-domain program that computes the relation.
  1.  { (aibi, ci) | i >= 0 }
  2.  { (xy, x) | xy is in {a, b}* and |x| = |y| }
  3.  { (x, y) | x and y are in {0, 1}*, |x| = |y|, and y/= xrev }
  
3.2.1
For each of the following relations give a (deterministic, if possible) pushdown transducer that computes the relation.
  1.  { (aibj, ajbi) | i, j >= 0 }
  2.  { (x, aibj) | x is in {a, b}*, i = (number of a's in x), and j = (number of b's in x) }
  3.  { (xyz, xyrevz) | xyz is in {a, b}* }
  4.  { (aibj, ck) | i <= k <= j }
  5.  { (aibj, ck) | k = min(i, j) }
  6.  { (w, ck) | w is in {a, b}*, and k = min(number of a's in w, number of b's in w) }
  7.  { (xy, yxrev) | x and y are in {a, b}* }
  8.  { (x, xrevx) | x is in {a, b}* }
  9.  { (x, y) | x and y are in {a, b}*, and y is a permutation of x }
 
3.2.2
Find a pushdown transducer that simulates the computations of the recursive finite-domain program of Figure 3.E.1. Assume that the variables have the domain {0, 1}, and the initial value 0.
  
call RP(x)                         /* I1 */
if eof then accept                      /* I2 */
reject                                          /* I3 */
procedure RP(y)
    read x                                     /* I4 */
    if x/= y then                         /* I5 */
        call RP(x)                   /* I6 */
    write y                                   /* I7 */
    return                                     /* I8 */
end
 
Figure 3.E.1
 
3.2.3
For each of the following languages find a (deterministic, if possible) pushdown automaton that accepts the language.
  1.  { vwwrev | v and w are in {a, b}*, and |w| > 0 }
  2.  { x | x is in {a, b}* and each prefix of x has at least as many a's as b's }
  3.  { aibjajbi | i, j > 0 }
  4.  { w | w is in {a, b}*, and w/= wrev }
  5.  { xxrev | x is accepted by the finite-state automaton of Figure 3.E.2 }
       
    [PICT]
    Figure 3.E.2
  6.  { x | x = xrev and x is accepted by the finite-state automaton of Figure 3.E.2 }
  
3.3.1
For each of the following languages construct a context-free grammar that generates the language.
  1.  { x#y | x and y are in {a, b}* and have the same number of a's }
  2.  { aibjck | i/= j or j/= k }
  3.  { x | x is in {a, b}* and each prefix of x has at least as many a's as b's }
  4.  { x#y | x and y are in {a, b}* and y is not a permutation of x }
  5.  { x#y | x and y are in {a, b}* and x/= y }
 
3.3.2
Find a Type 2 grammar that is equivalent to the context-free grammar G = <N, S, P, S>, whose production rules are given in Figure 3.E.3(a).
  

 S  -->   CD
    -->   a        S  -->   AB
C   -->   e        A  -->   BAB        S  -->   aASa
    -->   SC          -->   a             -->   b         S   -->   aA
    -->   b        B  -->   ABA       A   -->   aAa       A   -->   Sb
D   -->   CC          -->   b             -->   b             -->   ab
    (a)              (b)               (c)               (d)
 
Figure 3.E.3
 
3.3.3
Let G = <N, S, P, S> be the context-free grammar whose production rules are listed in Figure 3.E.3(b). Find a recursive finite-domain program and a pushdown automaton that accept the language generated by G.  
3.3.4
Let M be the pushdown automaton whose transition diagram is given in Figure 3.E.4.
   
[PICT]
Figure 3.E.4
Find a context-free grammar that generates L(M). 
3.3.5
Find a deterministic pushdown automaton that accepts the language generated by the grammar G = <N, S, P, S>, whose production rules are given in Figure 3.E.3(c). 
3.3.6
Let the program P and the grammar G be as in Example 3.3.5. Find a derivation in G that corresponds to an accepting computation of P on input bab.  
3.3.7
Find the context-free grammar that accepts the same language as the program P in Figure 3.E.5, according to the proof of Theorem 3.3.3. Assume that the domain of the variables is equal to {a, b}, with a as initial value.
  
do                                               /* I1 */
    call f(x)                                 /* I2 */
    if eof then accept                  /* I3 */
until false                        /* I4 */
procedure f(x)
    if x = b then                          /* I5 */
        return                                 /* I6 */
    read x                                     /* I7 */
    call f(x)                                 /* I8 */
    return                                     /* I9 */
end
 
Figure 3.E.5
  
3.4.1
Redo Example 3.4.1 for the case that G has the production rules listed in Figure 3.E.3(d) and w = a5b4.  
3.4.2
Show that each of the following sets is not a context-free language.
  1.  { anblct | t > l > n > 0 }
  2.  { aareva | a is in {a, b}* }
  3.  { abarevbrev | a and b are in {a, b}* }
  4.  { anaana | a is in {a, b}*, and n = (the number of a's in a) }
  5.  { a#b | a and b are in {a, b}* and b is a permutation of a }
  6.  { ab | The finite-state transducer whose transition diagram is given in Figure 3.E.6
       
    [PICT]
    Figure 3.E.6
    has output b on input a }
  7.  { an! | n >= 1 }
 
3.4.3
Show that the relation { (x, dn) | x is in {a, b, c}* and n = min(number of a's in x, number of b's in x, number of c's in x) } is not computable by a pushdown transducer.   
3.5.1
Show that the class of the relations computable by pushdown transducers is closed under each of the following operations Y.
  1.  Inverse, that is, Y(R) = R-1 = { (y, x) | (x, y) is in R }.
  2.  Composition , that is, Y(R1, R2) = { (x, y) | x = x1x2 and y = y1y2 for some (x1, y1) in R1 and some (x2, y2) in R2 }.
  3.  Reversal, that is, Y = { (xrev, yrev) | (x, y) is in R }.
 
3.5.2
Show that the class of context-free languages is not closed under the operation Y(L1, L2) = { xyzw | xz is in L1 and yw is in L2 }.  
3.5.3
Find a pushdown automaton that accepts the intersection of the language accepted by the pushdown automaton whose transition diagram is given in Figure 3.E.7(a), and the language accepted by the finite-state automaton whose transition diagram is given in Figure 3.5.1(b).
   
[PICT]
Figure 3.E.7
 
3.5.4
Let M be the deterministic pushdown automaton given in Figure 3.E.7(b). Find the pushdown automaton that accepts the complementation of L(M) in accordance with the proof of Theorem 3.5.2.  
3.5.5
Show that if a relation is computable by a deterministic pushdown transducer, then its complementation is computable by a pushdown transducer.   
3.6.1
Show that the membership problem is decidable for pushdown automata.  
3.6.2
Show that the single valuedness problem is decidable for finite-state transducers.  
3.6.3
Show that the equivalence problem for finite-state transducers is reducible to the equivalence problem for pushdown automata.

[next] [prev] [prev-tail] [front] [up]