COS3701
EXAM PACK
2025
, lOMoARcPSD|41752181
UNIVERSITY EXAMINATIONS
OCTOBER/NOVEMBER 2023
COS3701
Theoretical Computer Science III
Welcome to the COS3701 exam.
Examiner name: Ms DR Mokwana
Internal moderator name: Prof F Bankole
External moderator name: Mr M Walaza
This paper consists of 5 pages.
Total marks: 80
Number of pages:
Instructions:
• Sign the Honesty Declaration.
• This exam is a closed book exam
• IRIS invigilation app will be used for proctoring.
Additional student instructions
1. Students must upload their 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. Students are advised to preview 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.
10. 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.
11. 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 plagiarise, 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.
Downloaded by Enos ()
, lOMoARcPSD|41752181
COS3701 Oct/Nov 2023
Question 1 [16]
(a) Determine a regular expression for the language L over the alphabet {a, b} that starts
with an a and is a multiple of 3 in length.
For example,
aba, ababab, aaaaaa and abababababaa are words in L but
ab, aaab, aaaaabaaaaa, baa, and baabbaaba are not. (2)
(b) Design a deterministic finite automaton (DFA) that will recognise all and only the words
in L as defined above. (4)
(c) Use Theorem 21 to develop a context-free grammar (CFG) for the language L. (4)
(d) Convert the following CFG to Chomsky Normal Form (CNF):
S → bXbZ | aXaY
X → baY | abZ | Λ
Y → aaX
Z → bbX | Λ (6)
Question 2 [10]
Build a deterministic pushdown automata (DPDA) that accepts the language
L = {an+1 ban−1 bb | n ≥ 1} over the alphabet Σ = {a, b}. (10)
Question 3 [12]
The pumping lemma with length for context-free languages (CFLs) can be stated as follows:
Let L be a CFL generated by a CFG in CNF with p live productions.
Then any word w in L with length > 2p can be broken into five parts: w = uvxyz such that
length(vxy) ≤ 2p length(x) > 0
length(v) + length(y) > 0
and such that all the words uvnxynz with n ∈ {2, 3, 4, . . .} are also in the language L.
Use the pumping lemma with length to prove that the language.
L = {(a)n+1 (bb)n (aa)n | n ≥ 0}
over the alphabet Σ = {a, b} is non-context-free. Show all the cases. (12)
2
Open Rubric
Downloaded by Enos ()
, lOMoARcPSD|41752181
COS3701 Oct/Nov 2023
Question 4 [12]
(a) Consider the language L1 generated by CFG1 given below
S → aABbB
A → aA | Λ
B → bB | Λ
Is the language L1
1. regular and context free, or
2. nonregular and context free? (1)
(b) Explain why you made the selection in part (a) above. (2)
(c) Consider the language L2 generated by CFG2 given below
S → ABBAS | Λ
A→a
B→b
Is the language L2
regular and context free, or nonregular and context free? (1)
(d) Explain why you made the selection in part (c) above. (2)
(e) Use the CFGs from the questions above (parts (a) and (c)) to generate a CFG that
generates the union language Lu. (3)
(f) Is Lu
1. regular and context free,
2. nonregular and context free, or
3. noncontext free? (1)
(g) Explain why you made the selection in part (f) above. (3)
Question 5 [6]
Use the reformulated version of Theorem 42 to decide whether the grammar given below
generates any words. (6)
S → AC
A → CC
B → CD | b
C → DB
D→a
3
Downloaded by Enos ()
EXAM PACK
2025
, lOMoARcPSD|41752181
UNIVERSITY EXAMINATIONS
OCTOBER/NOVEMBER 2023
COS3701
Theoretical Computer Science III
Welcome to the COS3701 exam.
Examiner name: Ms DR Mokwana
Internal moderator name: Prof F Bankole
External moderator name: Mr M Walaza
This paper consists of 5 pages.
Total marks: 80
Number of pages:
Instructions:
• Sign the Honesty Declaration.
• This exam is a closed book exam
• IRIS invigilation app will be used for proctoring.
Additional student instructions
1. Students must upload their 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. Students are advised to preview 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.
10. 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.
11. 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 plagiarise, 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.
Downloaded by Enos ()
, lOMoARcPSD|41752181
COS3701 Oct/Nov 2023
Question 1 [16]
(a) Determine a regular expression for the language L over the alphabet {a, b} that starts
with an a and is a multiple of 3 in length.
For example,
aba, ababab, aaaaaa and abababababaa are words in L but
ab, aaab, aaaaabaaaaa, baa, and baabbaaba are not. (2)
(b) Design a deterministic finite automaton (DFA) that will recognise all and only the words
in L as defined above. (4)
(c) Use Theorem 21 to develop a context-free grammar (CFG) for the language L. (4)
(d) Convert the following CFG to Chomsky Normal Form (CNF):
S → bXbZ | aXaY
X → baY | abZ | Λ
Y → aaX
Z → bbX | Λ (6)
Question 2 [10]
Build a deterministic pushdown automata (DPDA) that accepts the language
L = {an+1 ban−1 bb | n ≥ 1} over the alphabet Σ = {a, b}. (10)
Question 3 [12]
The pumping lemma with length for context-free languages (CFLs) can be stated as follows:
Let L be a CFL generated by a CFG in CNF with p live productions.
Then any word w in L with length > 2p can be broken into five parts: w = uvxyz such that
length(vxy) ≤ 2p length(x) > 0
length(v) + length(y) > 0
and such that all the words uvnxynz with n ∈ {2, 3, 4, . . .} are also in the language L.
Use the pumping lemma with length to prove that the language.
L = {(a)n+1 (bb)n (aa)n | n ≥ 0}
over the alphabet Σ = {a, b} is non-context-free. Show all the cases. (12)
2
Open Rubric
Downloaded by Enos ()
, lOMoARcPSD|41752181
COS3701 Oct/Nov 2023
Question 4 [12]
(a) Consider the language L1 generated by CFG1 given below
S → aABbB
A → aA | Λ
B → bB | Λ
Is the language L1
1. regular and context free, or
2. nonregular and context free? (1)
(b) Explain why you made the selection in part (a) above. (2)
(c) Consider the language L2 generated by CFG2 given below
S → ABBAS | Λ
A→a
B→b
Is the language L2
regular and context free, or nonregular and context free? (1)
(d) Explain why you made the selection in part (c) above. (2)
(e) Use the CFGs from the questions above (parts (a) and (c)) to generate a CFG that
generates the union language Lu. (3)
(f) Is Lu
1. regular and context free,
2. nonregular and context free, or
3. noncontext free? (1)
(g) Explain why you made the selection in part (f) above. (3)
Question 5 [6]
Use the reformulated version of Theorem 42 to decide whether the grammar given below
generates any words. (6)
S → AC
A → CC
B → CD | b
C → DB
D→a
3
Downloaded by Enos ()
