COS Assignment 2 solution

COS2601 2023 Assignment 2
Discussion
Q1
a) The appropriate universal set for the language ODDnotAB is the set of all words over the
alphabet Σ = {a, b}.

b) The generator(s) of ODDnotAB are as follows:
i) The empty string ε.
ii) The single characters a and b.

c) The function on the universal set is defined as follows:
i) If x is a word in ODDnotAB, then ax is also in ODDnotAB.
ii) If x is a word in ODDnotAB, then bx is also in ODDnotAB.

d) Using these concepts, the recursive definition of the language ODDnotAB is as follows:

i) ε ∈ ODDnotAB
ii) a ∈ ODDnotAB
iii) b ∈ ODDnotAB
iv) If x ∈ ODDnotAB, then ax ∈ ODDnotAB
v) If x ∈ ODDnotAB, then bx ∈ ODDnotAB

This definition states that the language ODDnotAB includes the empty string ε, the single
characters a and b, and any word obtained by appending an 'a' or a 'b' to a word already in
ODDnotAB.


Q2
a) Recursive Definition of Set P:
We can define the set P of all positive integers greater than 0 recursively as follows:
Base Case: 1 is in P.
Recursive Case: If n is in P, then (n + 1) is also in P.
In simpler terms, the set P includes 1, and if a number n is in P, then the number (n + 1) is also in P.
b) Induction Principle:
The appropriate induction principle for this proof is the Principle of Mathematical Induction. It
consists of two steps:
1. Base Step: We need to show that the given statement holds true for the base case, which is n = 1.
2. Inductive Step: We assume that the statement is true for a particular positive integer k and then
prove that it holds for the next positive integer k + 1.
c) Proof by Mathematical Induction: