COS3701
EXAM PACK
2025
, UNIVERSITY EXAMINATIONS
Jan/Feb 2025
COS3701
THEORETICAL COMPUTER SCIENCE III
Welcome to the COS3701 examination
Date: 30 January 2025
Time: 14:00
Hours: 2 hours
Examiner name: Ms DR Mokwana
Internal moderator name: Dr TG Moape
This paper consists of 05 pages.
Total marks: 80
Instructions:
1. Upload your answer scripts in a single PDF file (answer scripts must not be password
protected or uploaded as “read only” files)
2. Incorrect file format and uncollated answer scripts will not be considered.
3. NO emailed scripts will be accepted.
4. Preview your submissions (answer scripts) to ensure legibility and that the correct answer
script file has been uploaded.
5. Incorrect answer scripts and/or submissions made on unofficial examinations platforms
(including the invigilator cell phone application) will not be marked and no opportunity will be
granted for resubmission. Only the last answer file uploaded within the stipulated submission
duration period will be marked.
6. Mark awarded for incomplete submission will be the student’s final mark. No opportunity for
resubmission will be granted.
7. Mark awarded for illegible scanned submission will be the student’s final mark. No
opportunity for resubmission will be granted.
8. Submissions will only be accepted from registered student accounts.
9. Students who have not utilised the proctoring tool will be deemed to have transgressed
Unisa’s examination rules and will have their marks withheld. If a student is found to have
been outside the proctoring tool for a total of 10 minutes during their examination session,
they will be considered to have violated Unisa’s examination rules and their marks will be
withheld. For examinations which use the IRIS invigilator system, IRIS must be recording
throughout the duration of the examination until the submission of the examinations scripts.
Students have 48 hours from the date of their examination to upload their invigilator results from
IRIS. Failure to do so will result in students deemed not to have utilized the proctoring tools.
Open Rubric
, COS3701
Jan/Feb 2025
Question 1. [18]
1.1. Determine a regular expression for the language L over the alphabet {a, b} that consists of
all words that start with the substring ba, then could have other substrings but must have at
least one bb and bb cannot be followed by an a.
Example of words in the language are babb, baabbbbb, baaaaaaaaabb, bababaabbbbb etc.
Examples of words that are not in the language are a, aba, bbab, aaabbbba, ababbbbaabb
etc. (3)
1.2. Design a deterministic finite automaton (DFA) that will recognise all of the words in L as
defined above. (5)
1.3. Use Theorem 21 to develop a context-free grammar (CFG) for the language L. (4)
1.4. Convert the following CFG to Chomsky Normal Form (CNF):
S -> aY | bXY
X -> XYZX | a
Y -> bXY | ∆
Z -> b | ∆ (6)
Question 2. [12]
Build a deterministic pushdown automaton (DPDA) that accepts the language
L = {(a)n(b)n+2a | n ≥ 1} over the alphabet ∑ = {a, b}
Question 3. [14]
Prove that the language L = {abna2nbn} is non-context free. Use the pumping lemma with length.
2
, COS3701
Jan/Feb 2025
Question 4 [10]
Consider the Turing Machine (TM) T (over the input alphabet Σ = {a, b}) given below.
Trace the execution of the TM on a few strings of as and bs so that you can see how it works and
answer the following questions.
a. What is the shortest word that would be accepted by T? (2)
b. What is accept(T )? (3)
c. What is reject(T )? (2)
d. What is loop(T )? (3)
Question 5 (14)
Build a Turing Machine (TM) that
• accepts all words in {an bn am | n ≥ 0; m > n}
• loops forever on all words starting with b, and
• rejects all other words.
Assume that the alphabet is Σ = {a, b}
3
EXAM PACK
2025
, UNIVERSITY EXAMINATIONS
Jan/Feb 2025
COS3701
THEORETICAL COMPUTER SCIENCE III
Welcome to the COS3701 examination
Date: 30 January 2025
Time: 14:00
Hours: 2 hours
Examiner name: Ms DR Mokwana
Internal moderator name: Dr TG Moape
This paper consists of 05 pages.
Total marks: 80
Instructions:
1. Upload your answer scripts in a single PDF file (answer scripts must not be password
protected or uploaded as “read only” files)
2. Incorrect file format and uncollated answer scripts will not be considered.
3. NO emailed scripts will be accepted.
4. Preview your submissions (answer scripts) to ensure legibility and that the correct answer
script file has been uploaded.
5. Incorrect answer scripts and/or submissions made on unofficial examinations platforms
(including the invigilator cell phone application) will not be marked and no opportunity will be
granted for resubmission. Only the last answer file uploaded within the stipulated submission
duration period will be marked.
6. Mark awarded for incomplete submission will be the student’s final mark. No opportunity for
resubmission will be granted.
7. Mark awarded for illegible scanned submission will be the student’s final mark. No
opportunity for resubmission will be granted.
8. Submissions will only be accepted from registered student accounts.
9. Students who have not utilised the proctoring tool will be deemed to have transgressed
Unisa’s examination rules and will have their marks withheld. If a student is found to have
been outside the proctoring tool for a total of 10 minutes during their examination session,
they will be considered to have violated Unisa’s examination rules and their marks will be
withheld. For examinations which use the IRIS invigilator system, IRIS must be recording
throughout the duration of the examination until the submission of the examinations scripts.
Students have 48 hours from the date of their examination to upload their invigilator results from
IRIS. Failure to do so will result in students deemed not to have utilized the proctoring tools.
Open Rubric
, COS3701
Jan/Feb 2025
Question 1. [18]
1.1. Determine a regular expression for the language L over the alphabet {a, b} that consists of
all words that start with the substring ba, then could have other substrings but must have at
least one bb and bb cannot be followed by an a.
Example of words in the language are babb, baabbbbb, baaaaaaaaabb, bababaabbbbb etc.
Examples of words that are not in the language are a, aba, bbab, aaabbbba, ababbbbaabb
etc. (3)
1.2. Design a deterministic finite automaton (DFA) that will recognise all of the words in L as
defined above. (5)
1.3. Use Theorem 21 to develop a context-free grammar (CFG) for the language L. (4)
1.4. Convert the following CFG to Chomsky Normal Form (CNF):
S -> aY | bXY
X -> XYZX | a
Y -> bXY | ∆
Z -> b | ∆ (6)
Question 2. [12]
Build a deterministic pushdown automaton (DPDA) that accepts the language
L = {(a)n(b)n+2a | n ≥ 1} over the alphabet ∑ = {a, b}
Question 3. [14]
Prove that the language L = {abna2nbn} is non-context free. Use the pumping lemma with length.
2
, COS3701
Jan/Feb 2025
Question 4 [10]
Consider the Turing Machine (TM) T (over the input alphabet Σ = {a, b}) given below.
Trace the execution of the TM on a few strings of as and bs so that you can see how it works and
answer the following questions.
a. What is the shortest word that would be accepted by T? (2)
b. What is accept(T )? (3)
c. What is reject(T )? (2)
d. What is loop(T )? (3)
Question 5 (14)
Build a Turing Machine (TM) that
• accepts all words in {an bn am | n ≥ 0; m > n}
• loops forever on all words starting with b, and
• rejects all other words.
Assume that the alphabet is Σ = {a, b}
3
