UNIVERSITY EXAMINATIONS
Jan/Feb 2023
COS3701
Theoretical Computer Science III
80 Marks
Duration 2 Hours
Welcome to the COS3701 exam.
Examiner name: Ms DR Mokwana
Internal moderator name: Prof F Bankole
This paper consists of 5 pages.
Instructions:
• Upload you 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 IRIS 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
, COS3701
Jan/Feb 2023
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 b but contain exactly one aa substring (and no other as).
Example of words in the language are aab, bbbaabbb, bbbbaabbbbbbbb etc.
Examples of words that are not in the language are a, aba, bbab, aaabbbb, baabbbbaabb
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 → aX Y | Y b
X → X ZY Z | a
Y → bY | Λ
Z →a|Λ (6)
Question 2 [10]
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 [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 uv n xy n z 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.
Jan/Feb 2023
COS3701
Theoretical Computer Science III
80 Marks
Duration 2 Hours
Welcome to the COS3701 exam.
Examiner name: Ms DR Mokwana
Internal moderator name: Prof F Bankole
This paper consists of 5 pages.
Instructions:
• Upload you 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 IRIS 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
, COS3701
Jan/Feb 2023
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 b but contain exactly one aa substring (and no other as).
Example of words in the language are aab, bbbaabbb, bbbbaabbbbbbbb etc.
Examples of words that are not in the language are a, aba, bbab, aaabbbb, baabbbbaabb
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 → aX Y | Y b
X → X ZY Z | a
Y → bY | Λ
Z →a|Λ (6)
Question 2 [10]
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 [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 uv n xy n z 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.
