COS3701
EXAM PACK
, UNIVERSITY EXAMINATIONS
OCTOBER/NOVEMBER 2025
COS3701
THEORETICAL COMPUTER SCIENCE III
Welcome to the COS3701 examination
Date: 28 October 2025
Time: 07:45
Hours: 2hrs
Examiner name: Ms DR Mokwana
Internal moderator name: Dr P Le Roux
External moderator name: Mr M Mabokela
This paper consists of 2 pages.
Total marks: 70
Instructions:
• Upload your answer script in a single PDF file format not password protected
• No emailed scripts will be marked
• Preview your submission to ensure legibility and correct script file has been uploaded
• Students who have not utilised invigilation app will be subjected to disciplinary
process
• Students suspected of dishonesty conduct during examination will be subjected to
disciplinary process
• Write neatly and legibly
• The mark for each question is in brackets next to the question
Additional student instructions
1. Incorrect file format and uncollated answer scripts will not be considered.
2. 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.
3. Students suspected of dishonest conduct during the examinations will be subjected to
disciplinary processes. Students may not communicate with any other person or
request assistance from any other person during their examinations. Plagiarism is a
violation of academic integrity and students who plagiarize, copy from published work
or Artificial Intelligence Software (eg ChatGPT) or online sources (eg course
material), will be in violation of the Policy on Academic Integrity and the Student
Disciplinary Code and may be referred to a disciplinary hearing. Unisa has a zero
tolerance for plagiarism and/or any other forms of academic dishonesty.
4. Listening to audio (music) and making use of audio-to-text software is strictly
prohibited during your examination session unless such usage of the software is
related to a student’s assistive device which has been so declared. Failure to do so
will be a transgression of Unisa’s examination rules and the student's marks will be
withheld.
5. Non-adherence to the processes for uploading assessment responses will not qualify
the student for any special concessions or future assessments.
,COS3701 Oct/Nov 2025
QUESTION 1 [12]
1.1. Draw Finite Automata (FA) for all words with the substring bab over the
alphabet ∑ = {a, b}.
(6)
1.2. Define Context Free Grammar (CFG) for the above (Question 1.1) Finite
Automata (FA) (6)
QUESTION 2 [12]
Convert the following Context Free Grammar (CFG) to Chomsky Norman Form
(CNF)
S ⭢ aX | Yb
X ⭢ ZXYZ | a
Y ⭢ bY | b | ᴧ
Z⭢a|ᴧ
Show all the three steps.
QUESTION 3 [14]
Build a deterministic pushdown automata (DPDA) that accepts the language L =
{a n+1(ba)n−1 bb | n ≥ 1} over the alphabet Σ = {a, b}.
QUESTION 4 [8]
Given that L1 = (aa)* and L2 = (a + b)*ab(a + b)*.
Find grammars for L1 and L2. Then use Theorem 37 to find L1L2.
3
, COS3701 Oct/Nov 2025
QUESTION 5 [10]
Using theorem 42 algorithm to determine whether the following grammar
generate any words.
S⭢ XY
X⭢ SY
Y⭢ SX
X⭢ a
Y⭢ b
QUESTION 6 [14]
Build a Turing Machine (TM) that
n n-1
• accepts all words in {b aa(ba) | n >1},
• loops forever on all words starting with a, and
• rejects all other words.
Assume that the alphabet is Σ = {a,b}.
@unisa
2025
3
EXAM PACK
, UNIVERSITY EXAMINATIONS
OCTOBER/NOVEMBER 2025
COS3701
THEORETICAL COMPUTER SCIENCE III
Welcome to the COS3701 examination
Date: 28 October 2025
Time: 07:45
Hours: 2hrs
Examiner name: Ms DR Mokwana
Internal moderator name: Dr P Le Roux
External moderator name: Mr M Mabokela
This paper consists of 2 pages.
Total marks: 70
Instructions:
• Upload your answer script in a single PDF file format not password protected
• No emailed scripts will be marked
• Preview your submission to ensure legibility and correct script file has been uploaded
• Students who have not utilised invigilation app will be subjected to disciplinary
process
• Students suspected of dishonesty conduct during examination will be subjected to
disciplinary process
• Write neatly and legibly
• The mark for each question is in brackets next to the question
Additional student instructions
1. Incorrect file format and uncollated answer scripts will not be considered.
2. 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.
3. Students suspected of dishonest conduct during the examinations will be subjected to
disciplinary processes. Students may not communicate with any other person or
request assistance from any other person during their examinations. Plagiarism is a
violation of academic integrity and students who plagiarize, copy from published work
or Artificial Intelligence Software (eg ChatGPT) or online sources (eg course
material), will be in violation of the Policy on Academic Integrity and the Student
Disciplinary Code and may be referred to a disciplinary hearing. Unisa has a zero
tolerance for plagiarism and/or any other forms of academic dishonesty.
4. Listening to audio (music) and making use of audio-to-text software is strictly
prohibited during your examination session unless such usage of the software is
related to a student’s assistive device which has been so declared. Failure to do so
will be a transgression of Unisa’s examination rules and the student's marks will be
withheld.
5. Non-adherence to the processes for uploading assessment responses will not qualify
the student for any special concessions or future assessments.
,COS3701 Oct/Nov 2025
QUESTION 1 [12]
1.1. Draw Finite Automata (FA) for all words with the substring bab over the
alphabet ∑ = {a, b}.
(6)
1.2. Define Context Free Grammar (CFG) for the above (Question 1.1) Finite
Automata (FA) (6)
QUESTION 2 [12]
Convert the following Context Free Grammar (CFG) to Chomsky Norman Form
(CNF)
S ⭢ aX | Yb
X ⭢ ZXYZ | a
Y ⭢ bY | b | ᴧ
Z⭢a|ᴧ
Show all the three steps.
QUESTION 3 [14]
Build a deterministic pushdown automata (DPDA) that accepts the language L =
{a n+1(ba)n−1 bb | n ≥ 1} over the alphabet Σ = {a, b}.
QUESTION 4 [8]
Given that L1 = (aa)* and L2 = (a + b)*ab(a + b)*.
Find grammars for L1 and L2. Then use Theorem 37 to find L1L2.
3
, COS3701 Oct/Nov 2025
QUESTION 5 [10]
Using theorem 42 algorithm to determine whether the following grammar
generate any words.
S⭢ XY
X⭢ SY
Y⭢ SX
X⭢ a
Y⭢ b
QUESTION 6 [14]
Build a Turing Machine (TM) that
n n-1
• accepts all words in {b aa(ba) | n >1},
• loops forever on all words starting with a, and
• rejects all other words.
Assume that the alphabet is Σ = {a,b}.
@unisa
2025
3
