• Wrong document? Swap it for free
  • Written by students who passed
  • Immediately available after payment
  • Read online or as PDF
  • 4,6 TrustPilot
0
Sell
Where do you study
Your language
Start selling Create your account
To add items to your wishlist, you must be logged in
Document preview thumbnail
Preview 4 out of 34 pages
Other

COS2601 Assignment 02 Solutions 2026

0,0
(0 reviews)
- sold
34 pages
2025/2026 Written for academic year
Institution University Of South Africa (Unisa)
Course Theoretical Computer Science II (COS2601)
Document preview thumbnail
Preview 4 out of 34 pages

COS2601 Assignment 02 Solutions 2026

Content preview

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

𝑏𝑎𝑏𝑏𝑎𝑎𝑏 ∉ 𝑆 ∗

Table of contents

  1. 01 QUESTION 1 2
    1. Question 1(a) - Membership in S* 2
    2. (i) baabababb 2
    3. (ii) babbaab 3
    4. Question 1(b) - Sets S and T 5
    5. Question 1(c) - Five-letter words in S* 6
  2. 02 QUESTION 2 9
    1. Question 2(a) - Regular expression evaluation 9
    2. Question 2(b) - Odd number of a's 11
    3. Question 2(c) - Language intersection 12
  3. 03 QUESTION 3 15
    1. Question 3(a) - Universal set 15
    2. Question 3(b) - Generators 15
    3. Question 3(c) - Recursive function 16
    4. Question 3(d) - Recursive definition 17
  4. 04 QUESTION 4 19
    1. Question 4(a) - Recursive definition of positive integers 19
    2. Question 4(b) - Principle of Mathematical Induction 19
    3. Question 4(c) - Induction proof 20
    4. Basis Step 20
    5. Induction Hypothesis 20
    6. Induction Step 20
    7. Conclusion 21
  5. 05 QUESTION 5 22
    1. Language analysis 22
    2. State definition 22
    3. Transition table 23
    4. State diagram and explanation 23
    5. Examples 24
  6. 06 QUESTION 6 25
    1. Language analysis 25
    2. DFA construction 25
    3. State definition 26
    4. Start transitions 26
    5. Prefix checking 26
    6. Length and suffix transitions 27
    7. Transition table 28
    8. Accepting state 28
    9. Examples 29
  7. 07 QUESTION 9 30
    1. Mealy machine transition table 30
    2. State splitting 30
    3. Moore machine states and outputs 30
    4. Moore machine transition table 31
    5. Moore machine diagram 31
  8. 08 QUESTION 10 33
    1. Transition expressions 33
    2. Eliminate state 2 33
    3. Eliminate state 5 33
    4. Eliminate state 3 33
    5. Account for loop at state 1 34
    6. Final regular expression 34

Document information

Uploaded on
July 10, 2026
Number of pages
34
Written in
2025/2026
Type
Other
Person
Unknown
Report Copyright Violation
R75,00
Wrong document? Swap it for free Within 14 days of purchase and before downloading, you can choose a different document. You can simply spend the amount again.
Written by students who passed
Immediately available after payment
Read online or as PDF
Seller avatar
Reputation scores are based on the amount of documents a seller has sold for a fee and the reviews they have received for those documents. There are three levels: Bronze, Silver and Gold. The better the reputation, the more your can rely on the quality of the sellers work.
iQlevel
4,2
(101)
Sold
792
Followers
31
Items
370
Last sold
3 weeks ago

Browse related subjects

Subjects

  • cos2601 assignment 02 solutions 2026

More courses for University of South Africa (Unisa) >

Why students choose Stuvia

Created by fellow students, verified by reviews

Quality you can trust: written by students who passed their exams and reviewed by others who've used these notes.

Didn't get what you expected? Choose another document

No worries! You can immediately select a different document that better matches what you need.

Pay how you prefer, start learning right away

No subscription, no commitments. Pay the way you're used to via credit card or EFT and download your PDF document instantly.

Student with book image

“Bought, downloaded, and aced it. It really can be that simple.”

Alisha Student

Working on your references?

Create accurate citations in APA, MLA and Harvard with our free citation generator.

Learn more Create citation
Working on your references?

Frequently asked questions