COS2601 Assignment 03 Due August 2026

UNIVERSITY OF SOUTH AFRICA
Department of Computer Science


⋄ ⋄ ⋄ ⋄ ⋄ ⋄ ⋄ ⋄ ⋄⋄


COS2601: Theoretical Computer Science II

Assignment | Year Module

⋄ ⋄ ⋄ ⋄ ⋄ ⋄ ⋄ ⋄ ⋄⋄




COS2601
Module Code:
Theoretical Computer Science II
Module Name:
3
Assignment Number:




Submitted in partial fulfilment of the require-
ments for Theoretical Computer Science II, UNISA

,UNISA | COS2601 Theoretical Computer Science II



Question 1 [10 marks]


1(a) Let S be a set of strings on {a, b} with S = {ba, bb, baa, bab, aba}. For each of the follow-
ing strings, state whether or not it is a word in S ∗ . Justify your answer.


(i) baabababb


The set is:



S = {ba, bb, baa, bab, aba}


A word belongs to S ∗ if it can be formed by concatenating zero or more words from S.

Consider:



baabababb


We try to divide it into words from S:



baabababb = baa · bab · b


The first two parts are valid:



baa ∈ S




bab ∈ S


However:



b∈
/S


Therefore, this decomposition does not work.

Try another possible decomposition:


Page 2 of 53

,UNISA | COS2601 Theoretical Computer Science II




baabababb = ba · aba · babb


Although:



ba ∈ S


and



aba ∈ S


we have:



babb ∈
/S


No decomposition into complete words from S is possible.



/ S∗
baabababb ∈


(ii) babbaab


Consider:



babbaab


We can write:



babbaab = bab · baa · b


Although:



bab ∈ S



Page 3 of 53

, UNISA | COS2601 Theoretical Computer Science II


and



baa ∈ S


the remaining string is:



b∈
/S


Therefore:



/ S∗
babbaab ∈


Thus, neither of the two given strings is a word in S ∗ .


1(b) Provide an example of two sets of strings S and T on {a, b} such that:


S⊈T


and



S ∗ ∩ T ∗ = (S ∩ T )∗


Take:



S = {a}


and



T = {b}


Clearly:



S⊈T

Page 4 of 53