COS2601 EXAM PACK 2023

COS2601
EXAM PACK
2023
QUESTIONS WITH ANSWERS
EMAIL:

,COS2601 EXAM
PACK 2023
LATEST QUESTIONS
AND ANSWERS
For queries or any assignment help
Email:

, COS2601/202/2


Dear student


Solutions to the questions of assignment 2 are provided in this tutorial letter.

For this assignment, the following questions were used for calculating a mark for the
assignment.

Question 1 11marks
Question 2 12 marks
Question 3 5 marks
Question 5 7 marks

TOTAL 35 marks

The rest of the questions were only commented on, and not allocated a mark. Remember
to do the “Automata” and “Pumping lemmas” tutorials which are available on a CD that
you should have received.

Everything of the best with your studies!

Regards
COS2601 team

Question 1

A recursive definition for the language AtLeast3EndBB over the alphabet ∑ = {a b} must be
compiled where AtLeast3EndBB has as elements all words that have at least three characters
and end with a bb-substring.

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

Answer 1

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

(ii) The generators are abb and bbb. Note that the generator(s) is/are always the shortest
word(s) in a language.

(iii) The function CONCAT as defined in learning unit 3, will be suitable. You can see how this
function has been used in Activity 3.1 in learning unit 3.

(iv) We give two possible recursive definitions. Note that we need to ensure that when we
concatenate strings to form new words that we do not generate words that end with a



2

, COS2601/202/2


single isolated bor an a– this would result in words ending on an ab- or a-substring, and
these words are not in AtLeast3EndBB.

We give two possible recursive definitions.

AtLeast3EndBB is the smallest subset of { a b}* such that
abb, bbb AtLeast3EndBB
and if w AtLeast3EndBB, then also
CONCAT( a, w), CONCAT( b, w), CONCAT( w, b)  AtLeast3EndBB.

or

Rule 1: abb, bbb AtLeast3EndBB
Rule 2: If w AtLeast3EndBB, then also
CONCAT( a, w), CONCAT( b, w), CONCAT( w, b)  AtLeast3EndBB.
Rule 3: Only words generated by rules 1 and 2 are in AtLeast3EndBB.


Question 2

This question has three parts and tests mathematical induction.

(i) Provide a recursive definition for the set P of all positive integers greater than 0,
(ii) formulate the appropriate induction principle, and then
(iii) apply the induction principle to prove that for each integer n > 0,
n 2 n(n + 1)(2n + 1)
 j =
j =1 6
.


Answer 2

(i) P is the smallest subset of R such that 1  P and if k  P then also
k+1  P.

Another correct recursive definition for P is:

Rule 1: 1 P
Rule 2: If k  P, then also k+1  P
Rule 3: Only elements generated by the above rules are in P.

(ii) The applicable induction principle is:

If a subset A of P is such that 1  A and if k  A then also k+1  A, then A = P.

(iii) Define A ⊆ P as follows:
n 2 n(n + 1)(2n + 1)
A = {n | n  P and j
j =1
=
6
}


We want to prove that this subset A of P is actually equal to P. The first step is to find out
whether the element 1 is in A. We do it as follows:



3