COS2601 Exam pack 2025(Theoretical Computer Science II)

COS2601 EXAM PACK
2025

QUESTIONS AND
ANSWERS
FOR ASSISTANCE CONTACT
EMAIL:

, lOMoARcPSD|50013335




COS2601 Example exam paper

EXAMPLE EXAMINATION PAPER and SOLUTIONS

QUESTION 1: Languages [10]

(a) Let S = {a, bb, bab, abaab}. For each of the following strings, state whether or not it is a word in
S*:

(i) abbabaabab
(ii) abaabbabbbaabb (2)

(i) No, because there are no concatenations of a, bb, bab and abaab that will yield the word
abbabaabab.

(ii) Yes, concatenations of a, bb, bab and abaab will yield the word: (abaab)(bab)(bb)(aa)(bb).

(b) Give an example of a set S such that S* only contains all possible strings of combinations of a’s
and b’s that have length divisible by three. (4)

There is only one possible set S: S = {aaa, aab, aba, abb, baa, bab, bba, bbb}. All the words in S* are
multiples of three as all the words of S are of length exactly 3.

(c) Give an example of two sets S and T of strings such that
S* = T* but S ⊄ T and T ⊄ S. (4)

We give two possible answers, there are many other possibilities:
S = {Λ, a} and T = {a, aa} or S = {a, b, ab} and T = {a, b, ba}.


QUESTION 2: Regular expressions [10]

(a) Does the regular expression
[b*+ (abb*)* + (aabb*)*]* bbb [b* + (abb*)* + (aabb*)*]*
define the language of all words in which the substring bbb appears at least once, but the
substring aaa does not appear at all? If not, give a counter-example. (5)

It is indeed the case that all words generated by the given regular expression contain the substring bbb.
It is furthermore the case that no word generated by the given regular expression contains the substring
aaa. However, not all such words (i.e. words containing the substring bbb but not the substring aaa) can
be generated by the given regular expression. Some examples are:
babbb
aabbb
bbba.
The answer to this question is thus no, and the words above serve as counterexamples.

(b) Give a regular expression generating the language consisting of all words containing exactly one
occurrence of the substring aa and no occurrence of the substring bb. (5)

The regular expression that we need to give, must make provision for words that start (and end) with
either an a or a b. All occurrences of the letter b (except if it is the last letter of the word) must be
followed by an a. Furthermore, only one a may be followed by another a - in order to ensure only one
occurrence of the substring aa. A possible regular expression is:
(b + Λ)(ab)*aa(ba)*(b + Λ)
This is of course not the only possibility.



1

, lOMoARcPSD|50013335




COS2601 Example exam paper

QUESTION 3: Recursive definitions [10]

A recursive definition for the language ODDAB should be compiled. Consider the alphabet ∑ = {a, b} and
the language ODDAB, where ODDAB consists of all words of odd length that contain the substring ab.
Provide

(i) an appropriate universal set, (1)
(ii) the generator(s) of ODDAB, (2)
(iii) an appropriate function on the universal set, and then (1)
(iv) use these concepts to write down a recursive definition for the language ODDAB. (6)

(i) The set {a, b}* will be suitable because it contains, along with other words, all the words that are
in the language ODDAB.

(ii) The generators should be the smallest words in ODDAB of odd length and should contain the
substring ab. Thus,
aba, aab, abb, bab
will be suitable generators.

(iii) The function CONCAT as defined in the study guide will be suitable.

(iv) We give two possible recursive definitions. Note that all words in ODDAB should have an odd
number of letters. The generators all have an odd number of letters; therefore, to keep the length
of new words odd, we concatenate two letters at a time. Note, the generator(s) is/are always the
smallest word(s) in a language.

ODDAB is the smallest subset of {a, b}* such that
aba, aab, abb, bab ∈ ODDAB, and if w ∈ ODDAB,
then also CONCAT(w,aa), CONCAT(w,bb), CONCAT(w,ab), CONCAT(w,ba),
CONCAT(aa,w), CONCAT(bb,w), CONCAT(ab,w), CONCAT(ba,w) ∈ ODDAB.

Or an alternative definition:
Rule 1: aba, aab, abb, bab ∈ ODDAB.

Rule 2: If w ∈ ODDAB, then also CONCAT(w,aa), CONCAT(w,bb), CONCAT(w,ab),
CONCAT(w,ba), CONCAT(aa,w), CONCAT(bb,w), CONCAT(ab,w),
CONCAT(ba,w) ∈ ODDAB.

Rule 3: Only words produced by rules 1 and 2 are in ODDAB.


QUESTION 4: Mathematical induction [10]

(i) Give a recursive definition of the set P of all positive integers greater than or equal to 5,
(1)
(ii) formulate an appropriate induction principle, and (2)
(iii) then apply the induction principle to prove that
2n – 3 ≤ 2n-2 for all integers n ≥ 5. (7)

(i) P is the smallest subset of Z (the set of integers) such that 5 ∈ P and if n ∈ P, then also n + 1 ∈ P.

(ii) If a subset A of P is such that 5 ∈ A and if n ∈ A, then also n + 1 ∈ A, then A = P.

(iii) Define A ⊆ P as follows:
A = {n ∈ P | 2n – 3 ≤ 2n-2}

2

, lOMoARcPSD|50013335




COS2601 Example exam paper

Show for n = 5
2(5) - 3 ≤ 25 - 2
i.e. 7 ≤ 8
Thus, 5 ∈ A is true.

Assume k ∈ A, i.e. we assume that 2k – 3 ≤ 2k – 2

Required to prove that k + 1 ∈ A, i.e. 2(k + 1) –3 ≤ 2(k + 1) – 2.

LHS
= 2(k + 1) – 3
= 2k + 2 – 3
= (2k – 3) + 2
≤ 2k – 2 + 2 (from induction assumption (1))
≤ 2⋅2 k – 2 (because the smallest value for 2 k – 2 with k = 5
is 2 5 – 2 = 8 and 2⋅8 = 16 > 10 = 25 – 2 + 2)
1+k–2
=2
= 2 (k +1) – 2 = RHS

Thus k + 1 ∈ A
Hence, A = P so we conclude that 2n - 3≤ 2n -2
for all integers n ≥ 5.


QUESTION 5: Finite automata [10]

Build an FA (finite automaton) that accepts the language of all words that satisfies both of the following
conditions:
• NO word contains the substring bba, and
• ALL words end with a double letter, thus all words end with either aa or bb.
Note: Only one FA must be build.

NOTE: If you provide a nondeterministic finite automata (NFA) or transition graph (TG) for (c), the
maximum mark you may be awarded is 2. Ensure that you build a deterministic FA.

CAI tutorial: Remember to use the CAI tutorial Automata available on CD or downloadable
from the web. In preparation to this question, you can navigate through all the sections in the
tutorial. Graphical illustrations are also provided. (Please refer to section 1 in this tutorial letter.)

We do not need to keep track of the number of letters that have been read at any stage - even or odd is
irrelevant for this question. A dead-end state is necessary to make provision for all words containing the
bba-substring. You should further keep in mind that words ending on aaa or bbb are, of course, also
permissible.

From the initial state 1, we move to state 2 with an a and to state 3 with a b. From state 2, we move to a
final state 4 with an a and if we read an a in the final state, we stay in the final state, because words such
as aaa and aaaa are permissible words in the language. From state 3, we move to a final state, state 5,
with a b and if we read a b in the final state, we stay in the final state, because words such as bbb and
bbbb are permissible words in the language. If, however, we read an a in state 5, we move to a dead-
end state, state 6, from which we cannot leave because then the word contains the impermissible
substring bba. The incomplete FA is given below:




3