lOMoAR cPSD| 32110785
Downloaded by Vincent Cosmas ()
, lOMoAR cPSD| 32110785
UNIVERSITY EXAMINATIONS
Jan/Feb 2025
COS3701
THEORETICAL COMPUTER SCIENCE III
Welcome to the COS3701 examination
Date: 30 January 2025
Time: 14:00
Hours: 2 hours
Examiner name: Ms DR Mokwana
Internal moderator name: Dr TG Moape
This paper consists of 05 pages.
Total marks: 80
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.
Downloaded by Vincent Cosmas ()
, lOMoAR cPSD| 32110785
4. Preview your 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.
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.
Open Rubric
Downloaded by Vincent Cosmas ()
, lOMoAR cPSD| 32110785
Question 1.
[18]
1.1. Determine a regular expression for the
language L over the alphabet {a, b} that consists
of all words that start with the substring ba, then
could have other substrings but must have at
least one bb and bb cannot be followed by an a.
Example of words in the language are babb,
baabbbbb, baaaaaaaaabb, bababaabbbbb etc.
Examples of words that are not in the language
are a, aba, bbab, aaabbbba, ababbbbaabb etc.
(3)
1.2. Design a deterministic finite automaton (DFA)
that will recognise all of the words in L as
defined above. (5)
1.3. Use Theorem 21 to develop a context-free grammar (4)
(CFG) for the language L.
1.4. Convert the following CFG to Chomsky Normal
Form (CNF):
S -> aY | bXY
X -> XYZX | a
Y -> bXY | ∆
Z -> b | ∆ (6)
Downloaded by Vincent Cosmas ()
Downloaded by Vincent Cosmas ()
, lOMoAR cPSD| 32110785
UNIVERSITY EXAMINATIONS
Jan/Feb 2025
COS3701
THEORETICAL COMPUTER SCIENCE III
Welcome to the COS3701 examination
Date: 30 January 2025
Time: 14:00
Hours: 2 hours
Examiner name: Ms DR Mokwana
Internal moderator name: Dr TG Moape
This paper consists of 05 pages.
Total marks: 80
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.
Downloaded by Vincent Cosmas ()
, lOMoAR cPSD| 32110785
4. Preview your 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.
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.
Open Rubric
Downloaded by Vincent Cosmas ()
, lOMoAR cPSD| 32110785
Question 1.
[18]
1.1. Determine a regular expression for the
language L over the alphabet {a, b} that consists
of all words that start with the substring ba, then
could have other substrings but must have at
least one bb and bb cannot be followed by an a.
Example of words in the language are babb,
baabbbbb, baaaaaaaaabb, bababaabbbbb etc.
Examples of words that are not in the language
are a, aba, bbab, aaabbbba, ababbbbaabb etc.
(3)
1.2. Design a deterministic finite automaton (DFA)
that will recognise all of the words in L as
defined above. (5)
1.3. Use Theorem 21 to develop a context-free grammar (4)
(CFG) for the language L.
1.4. Convert the following CFG to Chomsky Normal
Form (CNF):
S -> aY | bXY
X -> XYZX | a
Y -> bXY | ∆
Z -> b | ∆ (6)
Downloaded by Vincent Cosmas ()
