COS2601 Assignment 2 Year 2023

Question 1a
Universal Set:

The appropriate universal set for this language is the set of all possible strings over the alphabet Σ =
{a, b}. Let's denote this set as U.


Question 1b
The generators of ODDnotAB can be defined as follows:

The empty string ε is a generator of ODDnotAB.
For any string x in ODDnotAB, the strings xa and xb are also generators of ODDnotAB.


Question 1c
Function on the Universal Set:

We need to define a function on the universal set that determines whether a given string belongs to
ODDnotAB or not. Let's denote this function as isInODDnotAB(x), where x is a string from the
universal set U. The function isInODDnotAB(x) returns true if x belongs to ODDnotAB, and false
otherwise.


Question 1d
Recursive Definition of ODDnotAB:

Using the concepts described above, we can write the recursive definition for the language
ODDnotAB as follows:

1. Base Cases:
a) The empty string ε is in ODDnotAB.
isInODDnotAB(ε) = true
b) Strings of length 1:
For any single character string x, isInODDnotAB(x) = true.

2. Recursive Cases:
a) If x is a string in ODDnotAB, then the strings xa and xb are also in ODDnotAB.
isInODDnotAB(xa) = isInODDnotAB(x)
isInODDnotAB(xb) = isInODDnotAB(x)

b) If x is a string in ODDnotAB, then the strings xaa and xab are also in ODDnotAB.
isInODDnotAB(xaa) = isInODDnotAB(x)
isInODDnotAB(xab) = isInODDnotAB(x)

c) If x is a string in ODDnotAB, then the strings xba and xbb are also in ODDnotAB.
isInODDnotAB(xba) = isInODDnotAB(x)
isInODDnotAB(xbb) = isInODDnotAB(x)

By using these base cases and recursive cases, we can determine whether a given string belongs to the
language ODDnotAB or not.