Page 1 of 2

COSC 4111/5111 3.0—Fall 2001

Date: Sep 27, 2001 Due: End of October, 2001 [Exact date TBA]

Problem Set No. 1

Graduate students are required to do all these problems for full credit. Undergraduate students can get full credit without solving the problems marked “grad▶”. Conversely, undergraduates will get extra credit if they completely solve “grad problems”.

(1) Prove, using only the axioms of Kleene algebra, that (a^{∗}b^{∗})^{∗} = (a + b)^{∗} for any objects a and b in the underlying set.

Hint. Split = into ≤ and ≥.

(2) Kozen, p.315, #1.

(3) Kozen, p.320, #15 (Required method: Use the method of Kleene algebras to set up and solve an appropriate system of equations).

(4) grad▶ Use the Myhill-Nerode theorem (but no other method) to prove that if L is regular, then so is the language

{x : xy ∈ L}

(People often call the above language either the “prefix” or “initial” language of L.)

(5) Kozen, p.335, #80.

(6) grad▶ Prove a strengthened “uvwxy-theorem” (pumping Lemma) for CFLs: All in the theorem statement is to be as we know it, but the pumped components are to be guaranteed nonempty. Both of them, that is, v ≠ ε and x ≠ ε.

This problem is a bit open-ended, and may entail a bit of search in the literature (make sure you fully acknowledge your “sources”). One way to do it is to look into Greibach Normal Form (i.e., productions are of the type A → aγ where a ∈ Σ and γ ∈ V^{∗}) and see if you can (provably) get a normal form with productions like A → aγb instead, where b ∈ Σ.

(7) Show that in the presence of the initial functions the following operations can be simulated by composition:

(a) Substitution of a variable by a function

(b) Substitution of a variable by a constant

(c) Identification of any two variables

(d) Permutation of any two variables

(e) Introduction of new (“dummy”) variables

(NB. In class we looked at special cases of each of (7a)–(7e), i.e., cases of up to 2 variables. You are to argue the general case here.)

(8) Prove that λxyz. if x = 0 then y else z is in PR.

NOTE. For problem (8) only, please give the “fully (formally) dressed ” primitive recursion, along with an informal primitive recursion. An example of the latter (for predecessor) is

0 −^{·} 1 = 0
x + 1 −^{·} 1 = x

(9) Define

(μ^{∘}y)_{≤z}f(y, x⃗) =^{def} \begin{cases}min\{y : y ≤ z & f(y, x⃗) = 0\} \\ 0, if the min does not exist \end{cases}

Prove that PR is closed under (μ^{∘}y)_{≤z}.

(10) grad▶ (Tricky, but has a “one-line proof”) Prove that if a class of functions C is closed under (μ^{∘}y)_{≤z} and substitution, then its corresponding class of relations C_{∗} is closed under (∃y)_{≤z}.

(11) Show that if λx⃗y.y = f(x⃗) is in PR_{∗}, and f is total, and f(x⃗) ≤ g(x⃗) for all x⃗, where g ∈ PR, then f ∈ PR.

(12) Write a loop program which computes λx.⌊x/3⌋. The program must only allow instruction-types X = 0, X = X + 1, X = Y and Loop X … end. It must not nest the Loop-end instruction!

(13) grad▶ From “Computability” text: Page 82, #31.

(14) From “Computability” text: Page 82, #33.

Hint. Compute a few values by hand to see what pattern emerges for f.