COS2601 Assignment 02 Solutions 2026

COS2601 Assignment 2 Solutions 2026
UNISA

,QUESTION 1

(a)

Let

𝑆 = {𝑏𝑎, 𝑏𝑏, 𝑏𝑎𝑎, 𝑏𝑎𝑏, 𝑎𝑏𝑎}


Determine whether each string belongs to 𝑆 ∗ .

Recall:

• 𝑆 ∗ is the set of all strings obtained by concatenating zero or more words
from 𝑆.
• Therefore, if the given string can be split completely into words from 𝑆, then it
belongs to 𝑆 ∗ .



(i) baabababb

Attempt to split the string into words from 𝑆:

𝑏𝑎𝑎 𝑏𝑎𝑏 𝑎𝑏𝑏


The remaining part is

𝑎𝑏𝑏


but

𝑎𝑏𝑏 ∉ 𝑆.


Try another decomposition.

Beginning with

𝑏𝑎 ∣ 𝑎𝑏𝑎𝑏𝑎𝑏𝑏


Since

𝑏𝑎 ∈ 𝑆

,the remaining part is

𝑎𝑏𝑎𝑏𝑎𝑏𝑏


Split again:

𝑎𝑏𝑎 𝑏𝑎𝑏 𝑏


The remaining symbol is

𝑏


and

𝑏 ∉ 𝑆.


Try another possibility:

𝑏𝑎 ∣ 𝑏𝑎𝑎 ∣ 𝑏𝑎𝑏 ∣ 𝑏


Again,

𝑏 ∉ 𝑆.


There is no way to partition the whole string into members of 𝑆.

Therefore

𝑏𝑎𝑎𝑏𝑎𝑏𝑎𝑏𝑏 ∉ 𝑆 ∗



(ii) babbaab

Split as follows:

𝑏𝑎𝑏 𝑏𝑎𝑎


This gives

𝑏𝑎𝑏 + 𝑏𝑎𝑎 = 𝑏𝑎𝑏𝑏𝑎𝑎

, leaving

𝑏


which is not in 𝑆.

Try another decomposition.

Start with

𝑏𝑎


Remaining:

𝑏𝑏𝑎𝑎𝑏


Now split

𝑏𝑏 𝑎𝑎𝑏


Since

𝑎𝑎𝑏 ∉ 𝑆,


this fails.

Try

𝑏𝑎 ∣ 𝑏𝑎𝑏 ∣?


Remaining

𝑎𝑏


which is not in 𝑆.

No valid decomposition exists.

Hence

𝑏𝑎𝑏𝑏𝑎𝑎𝑏 ∉ 𝑆 ∗