Computer Science Qualifying Exam Foundations January 1995

1. Question. Prove or disprove that the following language is regular, where the alphabet is ∑ = {a, b, #}.

L = {x#y|x, y ∈ (a + b)^{∗} and y is a prefix of x}

Solution. L is not regular by the Pumping Lemma.

Proof: Assume L is regular. Let n be the P.L. constant. Pick z = z^{n}b#a^{n}b.

Adversary divides z = uvw such that |uv| ≤ n and k = |v| ≥ 1. Then v ∈ a^{+} because |uv| ≤ n.

By the P.L., uv^{2}w = a^{n+k}b#a^{n}b is not a prefix of a^{n+k}b, so uv^{2}w ∉ L. This contradicts the Pumping Lemma, so L is not regular.

2. Question. Give a context-sensitive grammar for the following language, where the alphabet is ∑ = {a, b, #}.

L = {x#x|x ∈ (a + b)^{∗}}

Solution.

S → A#a | B#b | #  Xa → aX
A → AaX | BaY | a  Xb → bX
B → AbX | BbY | b  Y a → aY
X# → #a  Y b → bY

Y # → #b Idea: The intermediate results look like x#x, except that the leftmost character in x is a variable A or B for a or b. For example: Aabab#aabab. This leftmost variable produces new characters in pairs: a with X together, and b and Y. Then, X or Y migrates to the right until it hits the # and produces a terminal.

Sample derivation:

S → B#b → BbY #b → AbXbY #b → abXbY #b → abbXY #b → abbX#bb → abb#abb

Alternate Solution.

S → SAa | SBb | #
aA → Aa  bA → Ab
aB → Ba  bB → Bb
#A → a# #B → b#

Note. The rules of a context-sensitive grammar require that |α| ≤ |β| in every production α → β. In particular, the production A → ϵ is not allowed.

3. Question. Construct a partial recursive function f : N → N such that (i) f is defined infinitely often and (ii) f grows faster than any total recursive function (meaning that there is not total recursive g such that f(n) ≤ g(n) for all n such that f(n) is defined), and prove your answer.

Solution. Let ϕ_{1}, ϕ_{2}, … be an effective enumeration of all partial recursive functions from N to N. Define

f(k) = ϕ_{k}(k) + 1

Claim 1: f is partial recursive because it is possible to effectively enumerate all partial recursive functions. Of course, if ϕ_{k}(k) is undefined, then f(k) is also undefined.

Claim 2: f is defined infinitely often. We know that K = {k|ϕ_{k}(k) halts } is undecideable. If f is defined only finitely often, then K is finite and hence decideable.

Claim 3: There is no total recurseive g that bounds f. If g is total recursive, then g = ϕ_{k} for some k, and further ϕ_{k}(k) is defined. But then f(k) > g(k).

Alternate Solution. Let M_{1}, M_{2}, … be an enumeration of all Turing machines. Define f′(k) to be the number of moves M_{k} makes on input k, or else undefined if M_{k}(k) does not halt. Claims 1–3 can also be proved for f′.

Note. (1) It is not possible to choose ϕ_{1}, ϕ_{2}, … to be an enumeration of all total recursive functions. (2) It is not possible to make f be total recursive.

4. Question. In the propositional calculus, let B = {0, 1} be the set of boolean values where 0 = false, 1 = true and 0 < 1. A boolean function f : B^{n} → B is called monotonic if

f(x_{1}, …, x_{i−1}, 0, x_{i+1}, …, x_{n}) ≤ f(x_{1}, …, x_{i−1}, 1, x_{i+1}, …, x_{n})

for all x_{1}, …, x_{n} ∈ B and for all 1 ≤ i ≤ n. That is, flipping an input to f from 0 to 1 can never flip the output of f from 1 to 0.

Prove that any monotonic boolean function (with any number of inputs) can be expressed using only the operators ∧, ∨, and the constants 0, 1 (and of course the inputs x_{1}, …, x_{n}).

Hint: Consider f(0, x_{2}, …, x_{n}) and f(1, x_{2}, …, x_{n}).

Solution. Proof by induction on n. Define the induction hypothesis as

P (n) ≡ any monotonic f : B^{n} → B can be expressed with ∧, ∨, 1, 0

Base (n = 0). The only boolean functions with 0 inputs are f = 0 and f = 1, and both of these are in the proper form.

Base (n = 1). The only boolean functions with 1 input are f(x) = 0, f(x) = 1, f(x) = x, and f(x) = ¬x. The first three are in the proper form and the last one is not monotonic.

Ind (n ≥ 2). Let f : B^{n} → B be monotonic. Then

f(x_{1}, x_{2}, …, x_{n}) ≡ f(0, x_{2}, …, x_{n}) ∨ [x_{1} ∧ f(1, x_{2}, …, x_{n})]

This can be verified by plugging in x_{1} = 0 and x_{1} = 1 into both sides of the above equation and using the property that f(x_{1}, …, x_{n}) is monotonic.

Further, both f(0, x_{2}, …, x_{n}) and f(1, x_{2}, …, x_{n}) are monotonic, which follows immediately from the fact that f(x_{1}, …, x_{n}) is monotonic.

By the induction hypothesis, f(0, x_{2}, …, x_{n}) and f(1, x_{2}, …, x_{n}) can be expressed with ∧, ∨, 1, 0, and the above formula only uses ∧ and ∨, so f(x_{1}, …, x_{n}) can be written with ∧, ∨, 1, 0.

5. Question. Let D be a cpo (complete partial order) and let D → D be the cpo of continuous functions mapping D into D. Let F, G ∈ D → D such that F approximates G. Prove that the least fixpoint of F approximates the least fixpoint of G.

Solution. Since F, G are monotonic, it is easy to prove by induction that for all i ∈ N, F^{i}(⊥) ⊑ F^{i+1}(⊥) and G^{i}(⊥) ⊑ G^{i+1}(⊥). Moreover, since F ⊆ G, we know that F (x) ⊑ G(x) for all x ∈ D. Hence, it is easy to prove by induction that for all i ∈ N that

F^{i+1}(⊥) ⊑ F (G^{i}(⊥)) ⊑ G^{i+1}(⊥)

.

Since F and G are continuous, their least fixpoints are the least upper bounds of the chains {F^{i}(⊥)|i ∈ N} and {G^{i}(⊥)|i ∈ N}, respectively. But the least upper bound of {G^{i}(⊥)|i ∈ N} must be an upper bound for {F^{i}(⊥)|i ∈ N} because every element of {F^{i}(⊥)|i ∈ N} is bounded by a corresponding element of {G^{i}(⊥)|i ∈ N} and the ⊑ relation is transitive. hence, the least upper bound of {F^{i}(⊥)|i ∈ N} must approximate the least upper bound of {G^{i}(⊥)|i ∈ N}, which is what we were asked to prove.

6. Question. A term M in the λ-calculus has the form defined by the grammar

M ::= x|(λx.M)|(MM)

where x ranges over a set of variables. The β reduction relation →_{β} on λ-terms is the compatible closure of the relation determined by the rule

((λx.M)N) →_{β} M[N/x]

where M[N/x] is the capture-avoiding substitution of N for the free occurrences of x in M.

A term M is in normal form if there is no term N such that M →_{β} N.

(a) Find a λ-term M that has both an infinite reduction sequence

M →_{β} M_{1} →_{β} M_{2} →_{β} ⋯ →_{β} M_{k} →_{β} ⋯

and a normal form

M →_{β} N_{1} →_{β} ⋯ →_{β} N_{n}

where N_{n} is in normal form. Show the infinite reduction sequence (at least the first few terms) and the reduction to normal form.

(b) Extend your solution in (a) to a λ-term M that has both an infinite nonrepeating reduction sequence

M →_{β} M_{1} →_{β} M_{2} →_{β} ⋯ →_{β} M_{k} →_{β} ⋯

and a normal form

M →_{β} N_{1} →_{β} ⋯ →_{β} N_{n}

An infinite reduction sequence

M_{1} →_{β} M_{2} →_{β} ⋯ →_{β} M_{k} →_{β} ⋯

is non-repeating iff M_{i} = M_{j} (syntactic identity) implies that i = j. Show the infinite reduction sequence and the reduction to normal form.

Solution.

(a) Let M = (λx.y)Ω where Ω = ((λx.xx)(λx.xx)). Clearly, M →_{β} y which is in

normal form, yet

M →_{β} M →_{β} M →_{β} ⋯

because Ω →_{β} Ω.

(b) Let M = (λx.y)Ω′ where Ω = (ΘΘ) and Θ = (λx.xxx). As above, M →_{β} y which is in normal form, yet

M →_{β} MΘ →_{β} MΘΘ →_{β} ⋯

because Ω′ →_{β} Ω′Θ.