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
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
