COS3701
EXAM PACK
Recent exam questions and answers
Summarised study notes
Exam tips and guidelines
+27 81 278 3372
DISCLAIMER & TERMS OF USE
1. Educational Aid: These study notes are designed to serve as educational aids and should not be considered as a
substitute for individual research, critical thinking, or professional guidance. Students are encouraged to
conduct their own extensive research and consult with their instructors or academic advisors for specific
assignment requirements.
2. Personal Responsibility: While every effort has been made to ensure the accuracy and reliability of the
information provided in these study notes, the seller cannot guarantee the completeness or correctness of all
the content. It is the responsibility of the buyer to verify the accuracy of the information and use their own
judgment when applying it to their assignments.
3. Academic Integrity: It is crucial for students to uphold academic integrity and adhere to their institution's
policies and guidelines regarding plagiarism, citation, and referencing. These study notes should be used as a
tool for learning and inspiration, but any direct reproduction of the content without proper acknowledgment and
citation may constitute academic misconduct.
4. Limited Liability: The seller of these study notes shall not be held liable for any direct or indirect damages,
losses, or consequences arising from the use of the notes. This includes, but is not limited to, poor grades,
academic penalties, or any other negative outcomes resulting from the application or misuse of the information
provide
]
, UNIVERSITY EXAMINATIONS
OCTOBER/NOVEMBER 2024
COS3701
Theoretical Computer Science III
Welcome to the COS3701 examination
Date: 05 November 2024
Time: 07:45
Hours: 2hrs
Examiner name: Daphney Rakoti Mokwana
Internal moderator name: Dr TG Moape
External moderator name:
This paper consists of 04 pages.
Total marks: 80
Number of pages:
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. 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.
, COS3701 Oct/Nov 2024
Question 1 [16]
a) Determine a regular expression for the language L over the alphabet {a; b} that
consists of all words that have at least one a but contain exactly one bb substring (and
no other as). Example of words in the language are bba, aaabbaaa, aaaabbaaaaaa
etc. Examples of words that are not in the language are b, a, bab, ab, aaabbbb,
abaaabaaaaa etc. (2)
b) Design a deterministic finite automaton (DFA) that will recognise all of 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 -> aXY | Yb
X -> XZYZ | a
Y -> bY | Λ
Z -> a | Λ (6)
Question 2 [12]
Build a deterministic pushdown automata (DPDA) that accepts the language L =
{(ab)n(aa)m(ba)n-1 | n ≥1;m ≥1} over the alphabet ∑ = {a; b}.
Question 3 [10]
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(b)2n+2(a)n-1 |n ≥ 1}
over the alphabet ∑ = {a, b} is non-context-free.
2
, COS3701 Oct/Nov 2024
Question 4 [6]
Use the reformulated version of Theorem 42 to decide whether the grammar given below
generates any words:
S -> XY
X -> SY
Y -> SX
X -> a
Y -> b
Question 5 [6]
Consider the Turing Machine (TM) T (over the input alphabet ∑ = {a; b}) given below.
a) What is the shortest word that would be accepted by T ? (1)
b) What is accept(T )? (2)
c) What is reject(T )? (2)
d) What is loop(T )? (1)
Question 6 [14]
Build a Turing Machine (TM) that
• accepts all words in {(b)n+2an | n ≥ 1},
• loops forever on all words starting with a, and
• rejects all other words.
Assume that the alphabet is ∑ = {a; b}.
3
EXAM PACK
Recent exam questions and answers
Summarised study notes
Exam tips and guidelines
+27 81 278 3372
DISCLAIMER & TERMS OF USE
1. Educational Aid: These study notes are designed to serve as educational aids and should not be considered as a
substitute for individual research, critical thinking, or professional guidance. Students are encouraged to
conduct their own extensive research and consult with their instructors or academic advisors for specific
assignment requirements.
2. Personal Responsibility: While every effort has been made to ensure the accuracy and reliability of the
information provided in these study notes, the seller cannot guarantee the completeness or correctness of all
the content. It is the responsibility of the buyer to verify the accuracy of the information and use their own
judgment when applying it to their assignments.
3. Academic Integrity: It is crucial for students to uphold academic integrity and adhere to their institution's
policies and guidelines regarding plagiarism, citation, and referencing. These study notes should be used as a
tool for learning and inspiration, but any direct reproduction of the content without proper acknowledgment and
citation may constitute academic misconduct.
4. Limited Liability: The seller of these study notes shall not be held liable for any direct or indirect damages,
losses, or consequences arising from the use of the notes. This includes, but is not limited to, poor grades,
academic penalties, or any other negative outcomes resulting from the application or misuse of the information
provide
]
, UNIVERSITY EXAMINATIONS
OCTOBER/NOVEMBER 2024
COS3701
Theoretical Computer Science III
Welcome to the COS3701 examination
Date: 05 November 2024
Time: 07:45
Hours: 2hrs
Examiner name: Daphney Rakoti Mokwana
Internal moderator name: Dr TG Moape
External moderator name:
This paper consists of 04 pages.
Total marks: 80
Number of pages:
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. 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.
, COS3701 Oct/Nov 2024
Question 1 [16]
a) Determine a regular expression for the language L over the alphabet {a; b} that
consists of all words that have at least one a but contain exactly one bb substring (and
no other as). Example of words in the language are bba, aaabbaaa, aaaabbaaaaaa
etc. Examples of words that are not in the language are b, a, bab, ab, aaabbbb,
abaaabaaaaa etc. (2)
b) Design a deterministic finite automaton (DFA) that will recognise all of 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 -> aXY | Yb
X -> XZYZ | a
Y -> bY | Λ
Z -> a | Λ (6)
Question 2 [12]
Build a deterministic pushdown automata (DPDA) that accepts the language L =
{(ab)n(aa)m(ba)n-1 | n ≥1;m ≥1} over the alphabet ∑ = {a; b}.
Question 3 [10]
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(b)2n+2(a)n-1 |n ≥ 1}
over the alphabet ∑ = {a, b} is non-context-free.
2
, COS3701 Oct/Nov 2024
Question 4 [6]
Use the reformulated version of Theorem 42 to decide whether the grammar given below
generates any words:
S -> XY
X -> SY
Y -> SX
X -> a
Y -> b
Question 5 [6]
Consider the Turing Machine (TM) T (over the input alphabet ∑ = {a; b}) given below.
a) What is the shortest word that would be accepted by T ? (1)
b) What is accept(T )? (2)
c) What is reject(T )? (2)
d) What is loop(T )? (1)
Question 6 [14]
Build a Turing Machine (TM) that
• accepts all words in {(b)n+2an | n ≥ 1},
• loops forever on all words starting with a, and
• rejects all other words.
Assume that the alphabet is ∑ = {a; b}.
3
