100%
COS3701
EXAM PACK
DISTINCTION QUALITY
UNISA EXAM
, UNISA
UNIVERSITY EXAMINATIONS
college of
science, engineering
and technology
January/February 2026
COS3701
THEORETICAL COMPUTER SCIENCE III
Welcome to the COS3701 examination
Date: 29 January 2026
Time: 10:00
Hours: 2hrs
Examiner name: Ms DR Mokwana
Internal moderator name: Dr P Le Roux
External moderator name: Mr M Mabokela
This paper consists of 3 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.
Open Rubric
,COS3701 Jan/Feb 2026
QUESTION 1 [12]
1.1. Draw Finite Automata (FA) for the language L over the alphabet {a, b}
that consists of all words that start with the substring ab and ends with an
a.
Example of words in the language are aba, abba, ababa, abbaaba,
abbbabbba, abbaaaaaaa, abbbbbbbba, etc.
Examples of words that are not in the language are a, abb, abaab, bbab,
aaabbbb, baabbbbaaba etc.
(6)
1.2. Define Context Free Grammar (CFG) for the above (Question 1.1) Finite
Automata (FA) (6)
QUESTION 2 [14]
Convert the following Context Free Grammar (CFG) to Chomsky Norman Form
(CNF)
S ⭢ aXYZb | bYa
X ⭢ ZY | a
Y ⭢ aY | ᴧ
Z⭢b|ᴧ
Show all the three steps.
QUESTION 3 [14]
Build a deterministic pushdown automaton (DPDA) that accepts the language
L = {am+1(ba)n an | n ≥ 1, m ≥ 0} over the alphabet Σ = {a, b}.
QUESTION 4 [8]
Given that:
L1 = (a + bb)* and
L2 = (aa)*b(a + b)*
Find the grammar that generates L1.L2
2
, COS3701 Jan/Feb 2026
QUESTION 5 [12]
Using theorem 42 algorithm to determine whether the following grammar
generate any words.
S⭢ AB
A⭢ BC
C⭢ DA
B⭢ CD
D⭢ a
A⭢ b
QUESTION 6 [10]
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
2026
3
COS3701
EXAM PACK
DISTINCTION QUALITY
UNISA EXAM
, UNISA
UNIVERSITY EXAMINATIONS
college of
science, engineering
and technology
January/February 2026
COS3701
THEORETICAL COMPUTER SCIENCE III
Welcome to the COS3701 examination
Date: 29 January 2026
Time: 10:00
Hours: 2hrs
Examiner name: Ms DR Mokwana
Internal moderator name: Dr P Le Roux
External moderator name: Mr M Mabokela
This paper consists of 3 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.
Open Rubric
,COS3701 Jan/Feb 2026
QUESTION 1 [12]
1.1. Draw Finite Automata (FA) for the language L over the alphabet {a, b}
that consists of all words that start with the substring ab and ends with an
a.
Example of words in the language are aba, abba, ababa, abbaaba,
abbbabbba, abbaaaaaaa, abbbbbbbba, etc.
Examples of words that are not in the language are a, abb, abaab, bbab,
aaabbbb, baabbbbaaba etc.
(6)
1.2. Define Context Free Grammar (CFG) for the above (Question 1.1) Finite
Automata (FA) (6)
QUESTION 2 [14]
Convert the following Context Free Grammar (CFG) to Chomsky Norman Form
(CNF)
S ⭢ aXYZb | bYa
X ⭢ ZY | a
Y ⭢ aY | ᴧ
Z⭢b|ᴧ
Show all the three steps.
QUESTION 3 [14]
Build a deterministic pushdown automaton (DPDA) that accepts the language
L = {am+1(ba)n an | n ≥ 1, m ≥ 0} over the alphabet Σ = {a, b}.
QUESTION 4 [8]
Given that:
L1 = (a + bb)* and
L2 = (aa)*b(a + b)*
Find the grammar that generates L1.L2
2
, COS3701 Jan/Feb 2026
QUESTION 5 [12]
Using theorem 42 algorithm to determine whether the following grammar
generate any words.
S⭢ AB
A⭢ BC
C⭢ DA
B⭢ CD
D⭢ a
A⭢ b
QUESTION 6 [10]
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
2026
3
