COS3701
EXAM PACK
Recent exam questions and answers
Summarised study notes
Exam tips and guidelines
+27 81 278 3372
DISCLAIMER & TERMS OF USE
Educational Aid: These study notes are intended to be used as educational resources and should not be seen as a
replacement for individual research, critical analysis, or professional consultation. Students are encouraged to perform
their own research and seek advice from their instructors or academic advisors for specific assignment guidelines.
Personal Responsibility: While every effort has been made to ensure the accuracy and reliability of the information in
these study notes, the seller does not guarantee the completeness or correctness of all content. The buyer is
responsible for verifying the accuracy of the information and exercising their own judgment when applying it to their
assignments.
Academic Integrity: It is essential for students to maintain academic integrity and follow their institution's policies
regarding plagiarism, citation, and referencing. These study notes should be used as learning tools and sources of
inspiration. Any direct reproduction of the content without proper citation and acknowledgment may be considered
academic misconduct.
Limited Liability: The seller shall not be liable for any direct or indirect damages, losses, or consequences arising from
the use of these notes. This includes, but is not limited to, poor academic performance, penalties, or any other negative
consequences resulting from the application or misuse of the information provided.
, 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
Recent exam questions and answers
Summarised study notes
Exam tips and guidelines
+27 81 278 3372
DISCLAIMER & TERMS OF USE
Educational Aid: These study notes are intended to be used as educational resources and should not be seen as a
replacement for individual research, critical analysis, or professional consultation. Students are encouraged to perform
their own research and seek advice from their instructors or academic advisors for specific assignment guidelines.
Personal Responsibility: While every effort has been made to ensure the accuracy and reliability of the information in
these study notes, the seller does not guarantee the completeness or correctness of all content. The buyer is
responsible for verifying the accuracy of the information and exercising their own judgment when applying it to their
assignments.
Academic Integrity: It is essential for students to maintain academic integrity and follow their institution's policies
regarding plagiarism, citation, and referencing. These study notes should be used as learning tools and sources of
inspiration. Any direct reproduction of the content without proper citation and acknowledgment may be considered
academic misconduct.
Limited Liability: The seller shall not be liable for any direct or indirect damages, losses, or consequences arising from
the use of these notes. This includes, but is not limited to, poor academic performance, penalties, or any other negative
consequences resulting from the application or misuse of the information provided.
, 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
