COS2601 Assignment 2 Solutions 2026
UNISA
Theory of Computability — Full Worked Solutions
, QUESTION 1 [10]
(a) S = {ba, bb, baa, bab, aba}. Determine whether each string is a word in S*.
(i) baabababb
A string is a word in S* if it can be written as a concatenation of one or more elements of S. We
attempt to factorise the string using only elements of S:
baabababb = baa · ba · ba · bb
Check each factor is an element of S: baa ∈ S ✓, ba ∈ S ✓, ba ∈ S ✓, bb ∈ S ✓.
Verifying the concatenation reproduces the original string:
baa + ba + ba + bb = baabababb ✓
Conclusion: baabababb IS a word in S*, since it equals baa·ba·ba·bb, a concatenation of elements
of S.
(ii) babbaab
We attempt every possible factorisation of babbaab using elements of S = {ba, bb, baa, bab, aba}.
The string begins 'ba...', so the first factor can only be ba, baa or bab (the only elements of S starting
with 'ba'):
• First factor bab (positions 1–3) → remainder = baab. This remainder must itself factor into S*. Its
own first factor can only be ba or baa (bab does not match, since position 6 is 'a' not 'b'). ba (pos 4–5)
leaves remainder 'ab', which is not in S. baa (pos 4–6) leaves remainder 'b', which is not in S (single
letters are never elements of S). Dead end.
• First factor baa (positions 1–3) is impossible, since position 3 of the string is 'b', not 'a' — baa
requires the 3rd symbol to be 'a'.
• First factor ba (positions 1–2) → remainder = bbaab. Its first factor can only be bb (the only element
of S beginning 'bb'; ba/baa/bab are impossible since position 4 is 'b' not 'a'). bb (pos 3–4) leaves
remainder 'aab'. The only element of S starting with 'a' is aba, but aab ≠ aba (3rd symbol differs).
Dead end.
Every possible first factor leads to a dead end, so no factorisation of babbaab into elements of S
exists.
Conclusion: babbaab is NOT a word in S*.
(b) Example of two sets S, T on {a,b} such that S ⊄ T and S*∩T* = (S∩T)*.
Let S = {a, aa} and T = {a}.
Check S ⊄ T: aa ∈ S but aa ∉ T, so S is not a subset of T. ✓
Compute each side:
• S∩T = {a}, so (S∩T)* = a*
• S* : since S = {a, aa}, every string of a's can be built from a and aa, so S* = a*
• T* = a* (since T = {a})
• S*∩T* = a* ∩ a* = a*
Conclusion: S*∩T* = a* = (S∩T)*, while S ⊄ T, as required.
(c) S = {a, bb, bab}. List all words in S* of exactly 5 letters.
Every word of S* is a concatenation of copies of a (length 1), bb (length 2) and bab (length 3). We
need all combinations of these lengths that sum to 5, and for each combination, every ordering of the
pieces:
Case 1+1+1+1+1 (five a's):
aaaaa
UNISA
Theory of Computability — Full Worked Solutions
, QUESTION 1 [10]
(a) S = {ba, bb, baa, bab, aba}. Determine whether each string is a word in S*.
(i) baabababb
A string is a word in S* if it can be written as a concatenation of one or more elements of S. We
attempt to factorise the string using only elements of S:
baabababb = baa · ba · ba · bb
Check each factor is an element of S: baa ∈ S ✓, ba ∈ S ✓, ba ∈ S ✓, bb ∈ S ✓.
Verifying the concatenation reproduces the original string:
baa + ba + ba + bb = baabababb ✓
Conclusion: baabababb IS a word in S*, since it equals baa·ba·ba·bb, a concatenation of elements
of S.
(ii) babbaab
We attempt every possible factorisation of babbaab using elements of S = {ba, bb, baa, bab, aba}.
The string begins 'ba...', so the first factor can only be ba, baa or bab (the only elements of S starting
with 'ba'):
• First factor bab (positions 1–3) → remainder = baab. This remainder must itself factor into S*. Its
own first factor can only be ba or baa (bab does not match, since position 6 is 'a' not 'b'). ba (pos 4–5)
leaves remainder 'ab', which is not in S. baa (pos 4–6) leaves remainder 'b', which is not in S (single
letters are never elements of S). Dead end.
• First factor baa (positions 1–3) is impossible, since position 3 of the string is 'b', not 'a' — baa
requires the 3rd symbol to be 'a'.
• First factor ba (positions 1–2) → remainder = bbaab. Its first factor can only be bb (the only element
of S beginning 'bb'; ba/baa/bab are impossible since position 4 is 'b' not 'a'). bb (pos 3–4) leaves
remainder 'aab'. The only element of S starting with 'a' is aba, but aab ≠ aba (3rd symbol differs).
Dead end.
Every possible first factor leads to a dead end, so no factorisation of babbaab into elements of S
exists.
Conclusion: babbaab is NOT a word in S*.
(b) Example of two sets S, T on {a,b} such that S ⊄ T and S*∩T* = (S∩T)*.
Let S = {a, aa} and T = {a}.
Check S ⊄ T: aa ∈ S but aa ∉ T, so S is not a subset of T. ✓
Compute each side:
• S∩T = {a}, so (S∩T)* = a*
• S* : since S = {a, aa}, every string of a's can be built from a and aa, so S* = a*
• T* = a* (since T = {a})
• S*∩T* = a* ∩ a* = a*
Conclusion: S*∩T* = a* = (S∩T)*, while S ⊄ T, as required.
(c) S = {a, bb, bab}. List all words in S* of exactly 5 letters.
Every word of S* is a concatenation of copies of a (length 1), bb (length 2) and bab (length 3). We
need all combinations of these lengths that sum to 5, and for each combination, every ordering of the
pieces:
Case 1+1+1+1+1 (five a's):
aaaaa
