IU/CSD Qualifier Exam --- FOUNDATIONS
January 1996

Write to the point, but remember that unexplained answers do not get credit.

1. Let be a finite set of alphabet symbols. Exhibit a grammar that generates exactly the language consisting of regular expressions over the alphabet A.

2. Prove that the class of regular languages is closed under homomorphisms. Give an important application of this closure property.
   [Recall that a homomorphism h from to is a function such that for all .]

3. Exhibit a subclass of the context-free grammars that is commonly used to specify the syntax of programming languages. What is the most important property of these grammars that makes them suitable for that purpose?

4. State the Pumping Lemma for context-free languages. Exhibit a language that is not context-free and prove your claim using the Pumping Lemma.

5. Some desirable properties of computation models are:
   (i) Every intuitively computable function is computable by some device in ;
   (ii) Every device is represented by a finite syntactic object;
   (iii) It is effectively decidable whether a given syntactic object is a device in ;
   (iv) All functions computable by devices in are total.
   1. Prove that there is no computation model that satisfies all four properties above.
   2. For each property, exhibit a computation models that, albeit failing that property, satisfies the three remaining properties.

6. For each of the following conditions, tell whether there exists a LISP program which on input M returns 1 if M is the syntactic description of a Turing machine that satisfies the condition, and 0 if M is the syntactic description of a Turing machine that does not. Carefully explain your reasons, and the broad assumptions and major results you use. Do not enter into particular coding details. Let us write for the machine described by M. We posit a Turing machine model where nondeterminism is permitted.
   1. terminates on some input.
   2. terminates on all input.
   3. terminates on input M.
   4. M has a deterministic transition relation (table).
   5. has a deterministic computation on all input (that is, every configuration reached in any computation sequence has at most one permissible subsequent configuration).

7. 1. Define the notion of an NP-complete problem.
   2. Let the basic numeric expressions be the ones formed from variables and 1 using + and . Show that the problem of determining, given a basic numeric expression, whether it yields an even value for some values for the variables, is NP complete.

8. In the Town of Foobarton no artist is a beekeeper, but every beekeeper is a chemist. The mayor, himself a beekeeper, has just declared that there is a chemist in town who is not an artist. Transcribe the information about Foobarton, and the mayor's statement, into first order formulas, and prove that the latter follows from the former.

9. Let V be a vocabulary, and a denotable V-structure (i.e., every element of the universe is the denotation of some closed V-term). Exhibit a first order theory D such that a structure is a model of D iff has a substructure isomorphic to .

• About this document ...