Assignment 1

1. (3p) [AB] Prove using induction that, for every finite alphabet Σ, ∀ n ∈ ℕ. |Σⁿ| = |Σ|ⁿ.

2. [AB] Define a language S containing words over the alphabet Σ = {a, b} inductively in the following way:

   • The empty word is in S: ε ∈ S.

   • If u, v ∈ S, then auavb ∈ S.

   • If u, v, w ∈ S, then buavaw ∈ S.

   1. (1p) Use recursion to define two functions #_a, #_b ∈ Σ^* → ℕ that return the number of occurrences of a and b, respectively, in their input.

   2. (2p) Use induction to prove that ∀ w ∈ S. #_a(w) = 2 #_b(w).

      Hint: You might want to show that #_a(auavb) = 2 + #_a(u) + #_a(v). How do you prove this? This property follows from a lemma that you can perhaps prove by induction: ∀u, v ∈ Σ^*.#_a(uv) = #_a(u) + #_a(v).

3. [AB] Let Σ = {0} and define f, g, h ∈ Σ^* → ℕ recursively in the following way:

   • g(ε) = 1
     g(0w) = |w| + g(w) - h(w)

   • h(ε) = 0
     h(0w) = |w| + g(w)

   • f(ε) = 1
     f(0w) = h(w) + 2g(w)

   1. (0.5p) Compute the values of f(00), g(00), h(00), f(000), g(000), h(000), f(0000), g(0000) and h(0000).

   2. (3.5p) Prove that ∀ n ∈ ℕ. f(0ⁿ) = 1 + n.

      Hint: First prove that ∀ n ∈ ℕ. g(0ⁿ) = 1 ∧ h(0ⁿ) = n.

(Exercises marked with [AB] are based on exercises from a previous version of this course, given by Ana Bove.)