UNIVERSITY OF SOUTH AFRICA (UNISA)
Department of Computer Science
⋄
Theoretical Computer Science II
COS2601 — Year Module
⋄
Module Code: COS2601
Module Name: Theoretical Computer Science II
Module Type: Year Module
Department: Department of Computer Science
Submitted in partial fulfilment of the requirements for Theoretical Computer Science II
at the University of South Africa.
,UNISA | COS2601 Theoretical Computer Science II
Question 1 [10]
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 1 of 51
,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 2 of 51
, 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 3 of 51
Department of Computer Science
⋄
Theoretical Computer Science II
COS2601 — Year Module
⋄
Module Code: COS2601
Module Name: Theoretical Computer Science II
Module Type: Year Module
Department: Department of Computer Science
Submitted in partial fulfilment of the requirements for Theoretical Computer Science II
at the University of South Africa.
,UNISA | COS2601 Theoretical Computer Science II
Question 1 [10]
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 1 of 51
,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 2 of 51
, 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 3 of 51
