CSCI 4602
Fall 2001
Solutons to practice questions for quiz 3

1. Let BAL be the set of all strings of left and right parentheses that are balanced. A string of parentheses that is balanced requires not only a right parenthesis for each left parenthesis, but also correct nesting. Here is a context-free grammar that describes BAL.

        S  -> S S
        S  -> ( S )
        S  -> epsilon
     

   (where epsilon is the empty string). show a derivation and a parse tree for string (())(()()).

   Here is a leftmost derivation.

        S => S S
          => ( S ) S
          => ( ( S ) ) S
          => ( ( ) ) S
          => ( ( ) ) ( S )
          => ( ( ) ) ( S S )
          => ( ( ) ) ( ( S ) S )
          => ( ( ) ) ( ( ) S )
          => ( ( ) ) ( ( ) ( S ) )
          => ( ( ) ) ( ( ) ( ) )
     

   A parse tree looks like this.

                             S
                            / \
                           /   \
                          /     \
                         /       \
                        S         S
                       /|\       /|\
                      / | \     / | \
                     (  S  )   (  S  )
                       /|\       / \
                      / | \     /   \ 
                     (  S  )   S     S
                        |     /|\   /|\
                       eps   ( S ) ( S )           
                               |     |
                              eps   eps
     

   where eps stands for epsilon.

2. Give a context-free grammar for the language {w#x | w and x are strings over alphabet {a,b}, and w^R is a substring of x}. The alphabet of this language is {a,b,#}. Another way to describe the same language is {w#xw^Ry | w,x,y in {a,b}*}.

   Concentrate on the ww^R part. That can be generated by sitting in the middle, pushing the same character to the left and the right. That is done by nonterminal X in the following grammar. The part between w and w^R is generated by Z, which X becomes when it is done. The part after W^R is generated by S before starting X.

       S -> SY  | X
       X -> aXa | bXb | Z
       Y -> a | b
       Z -> ZY  | #
     

3. Briefly explain what the Church/Turing thesis says. Does it say that all models of computing have the same power? Is it possible to design and implement a language that offers less power than a Turing machine? More power?

   The Church/Turing thesis says that problems solvable algorithmically are exactly those problems solvable by Turing machines.

4. Does a computer with two stacks have the same, less or more power than a computer with one tape?

   A computer with two stacks has exactly the same power as a machine with one tape.

5. Consider restricted C++ programs that are only allowed to print "yes" or "no", and must terminate immediately after printing their answer. Is it possible to write a program that reads the text of such a C++ program p and tells whether or not p will print "yes" when run on an empty input? Justify your answer.

   No such program can be written. The set of programs on which it would have to answer yes respects equivalence and is nontrivial. It respects equivalence because if p and q are two equivalent programs and one of the answers yes on an empty input then the other also answers yes on an empty input. It is nontrivial because some programs answer yes on an empty input and some do not. Hence, it is undecidable to determine whether a program answers yes on an empty input.

6. Let A = {p | p(x) loops forever whenever the first letter of x is 'a'}. Is A decidable? Justify your answer.

   No, A is not decidable. A respects equivalence and is nontrivial.