Qualifier Exam --- FOUNDATIONS
SAMPLE, October 1995

1. In this question be sure to distinguish between a language and a grammar or automaton generating it. Justify all your answers at a level of detail suitable for a knowledgeable reader.
   1. Explain how each grammar and each automaton can be viewed as a finite set of finite strings.
   2. Define the notion of regular expression.
   3. Sketch an algorithm that when given a finite-state automaton converts it into an equivalent regular expression. Give an upper bound on the number of unions and concatenations in the output regular expression.
   4. Consider (without necessarily describing it) an algorithm that, given a context-free grammar G in Chomsky Normal Form and a string x, determines whether . Give an upper bound on the number of set products that the algorithm computes as a function of the sizes of G and x. Give an upper bound on the number of set products computed by the algorithm.

2. 1. Define the notions of problem, poly-time reductions between problems, and NP-completeness.
   2. Let us say that a boolean expression with an even number of variables is symmetric-satisfiable if there is a truth-valuation that satisfies , and under which exactly half of 's variables are assigned the value true. Show that symmetric satisfiability is NP-complete. (You may use without proof well-known examples of NP-complete problems.)

3. Let C be the set of descriptions of those Turing machines that converge for some input.
   1. Is the set C decidable?
   2. Is it semi-decidable (i.e. recursively enumerable)?
   3. Let D be the set of descriptions of those Turing machines that converge for no input. Is D semi-decidable?

4. 1. Is the following formula of first order logic provable?

      

      If it is, exhibit a complete formal proof for it. If it is not, give a structure in which the formula is false, where the universe of has exactly two elements.

   2. Same question for the formula
      
   3. Raymond Smullyan has observed that in every party he has been to, there was always some person p such that if p drank, then everyone drank. Using to express ``person p drinks'', write a first order formula that conveys Smullyan's observation. Is your formula provable? Answer as in the previous parts.

5. It is known that the provability of formulas of first order logic is undecidable.
   1. Is there a program that, when given a formula as input, returns 1 if is valid (that is, true in all structures) and 0 if it is not?
   2. Is there a program that when given a formula as input, returns 1 if is valid, and does not terminate if it is not?
   3. Is there a program that, when given a formula as input, returns 1 if is valid, and 0 if there is a finite structure in which is false?
   Explain your answers convincingly.

• About this document ...