CSCI 4602
Fall 2001
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 (())(()()).

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}*}.

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?

4. Does a computer with two stacks have the same, less or more power than a computer 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.

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