⋆
]]
⋆
COS3701: Theoretical Computer Science III
OCT/NOV Examination 2026 Preparation Guide
Covers Past Papers: Oct/Nov 2023 to Oct/Nov 2025
⋆ ⋄ ⋆ ⋄ ⋆ ⋄ ⋆ ⋄ ⋆
[ Computer Science — Automata & Formal Languages [
_ Exam Revision Guide
COS3701
Module Code:
Theoretical Computer Science III
Module Name:
Oct/Nov 2023 & Oct/Nov 2024
Papers Covered:
For Oct/Nov
Predictions:
80 per paper
Total Marks:
2 Hours
Duration:
Study the patterns. Understand the logic. Practise the diagrams.
Exam Revision Notes | COS3701 | 2023–2026
,COS3701 | Exam Revision 2023–2025 Theoretical Computer Science III
PAPER 1 — OCTOBER/NOVEMBER 2024
University Examinations · 05 November 2024 · 80 Marks · 2 Hours
Examiner: DR Mokwana Internal Moderator: Dr TG Moape
Page 2 of 30
,COS3701 | Exam Revision 2023–2025 Theoretical Computer Science III
Question 1 [16 marks]
(a) [2 marks]
Question: 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 bs appear consecutively). Example words: bba, aaabbaaa, aaaabbaaaaaa.
Non-examples: b, a, bab, ab, aaabbbb, abaaabaaaaa.
Answer:
Key Concept
A regular expression describes a regular language using concatenation, union (+),
and Kleene star (∗ ). Key constraint here: exactly one bb, at least one a, no other
adjacent bs.
The language L requires:
• Exactly one occurrence of bb (no bbb, no two separate bb)
• At least one a somewhere in the word
• bs only appear as single b or in the single bb block
Structure: Any b outside the bb block must be isolated (i.e. single). Segments between as
can contain at most one b.
Single-b (non-consecutive) segments over a and b: (a+ b)∗ a∗ (never two consecutive bs).
Let SAFE = a∗ (ba+ )∗ be the pattern of as and isolated bs.
The full expression (one bb block, at least one a):
SAFE · bb · SAFE where at least one a appears in the whole word
Since the bb block itself has no a, the a must come from SAFE. Refined:
RE = a∗ (ba+ )∗ bb a∗ (ba+ )∗ + (a+ (ba+ )∗ )∗ bb a∗ (ba+ )∗
A clean single expression enforcing at least one a overall and exactly one bb:
a∗ (ba+ )∗ bb a+ (ba+ )∗ + a+ (ba+ )∗ bb a∗ (ba+ )∗
Page 3 of 30
,COS3701 | Exam Revision 2023–2025 Theoretical Computer Science III
Both alternatives ensure at least one a is present; the bb block is unique because SAFE never
allows two consecutive bs.
⋆ Exam Tip
Full marks usually require: (1) showing the bb block is isolated, (2) demonstrating at
least one a, and (3) ensuring no extra consecutive bs. Show your reasoning clearly.
(b) [4 marks]
Question: Design a Deterministic Finite Automaton (DFA) that recognises all words in
L as defined above.
Answer:
Key Concept
A DFA has states, transitions on each symbol, one start state, and accept states. Every
input must lead to exactly one transition.
State design strategy:
• Track: (i) whether we have seen a bb, (ii) whether we have seen an a, (iii) how many con-
secutive bs we are currently reading, (iv) dead/trap state for invalid input.
States:
State Meaning
q0 Start: no a seen, no bb seen, no pending b
q1 No a seen, no bb seen, one b pending
q2 a seen, no bb yet, no pending b
q3 a seen, no bb yet, one b pending
q4 a seen (possibly), exactly one bb seen, no trailing b
q5 a seen, one bb seen, one b pending
DEAD Invalid (second bb or bbb)
Accept state: q4 (has seen at least one a and exactly one bb). Note: q5 is not accepting be-
cause a trailing b after bb is only ok if single — we accept when we confirm no more bb.
Key transitions:
a b
• q0 −
→ q2 ; q0 →
− q1
Page 4 of 30
,COS3701 | Exam Revision 2023–2025 Theoretical Computer Science III
b a
− DEAD (would be bb but no a yet);
• q1 → q1 −
→ q2
a b
→ q2 ;
• q2 − q2 →
− q3
b a
− q4 (bb found, a was already seen);
• q3 → q3 −
→ q2
a b
→ q4 ;
• q4 − q4 →
− q5
b a
− DEAD (second bb);
• q5 → q5 −
→ q4
a,b
• DEAD −−→ DEAD
⋆ Exam Tip
Draw the DFA clearly with arrows, label all transitions on each symbol, circle accept
states with double circles. A state diagram earns full marks; a transition table alone
may lose marks.
(c) [4 marks]
Question: Use Theorem 21 to develop a Context-Free Grammar (CFG) for the language
L.
Answer:
Key Concept
Theorem 21 states that every regular language is context-free. A DFA/NFA can be
converted to a CFG: each state qi becomes a non-terminal Qi . For each transition
x
→ qj , add production Qi → x Qj . For each accept state qi , add Qi → Λ.
qi −
Using the DFA above and Theorem 21:
Q0 → a Q2 | b Q1
Q1 → a Q2
Q2 → a Q2 | b Q3 | Λ (if q2 could be accept, but it’s not — remove Λ)
Q3 → b Q4 | a Q2
Q4 → a Q4 | b Q5 | Λ (accept state)
Q5 → a Q4
Note: Q4 is the only accept state, so Q4 → Λ is the only Λ production. The start non-
Page 5 of 30
, COS3701 | Exam Revision 2023–2025 Theoretical Computer Science III
terminal is Q0 .
(d) [6 marks]
Question: Convert the following CFG to Chomsky Normal Form (CNF):
S → aXY | Y b, X → XZY Z | a, Y → bY | Λ, Z→a|Λ
Answer:
Key Concept
Chomsky Normal Form (CNF): All productions are either A → BC (two non-
terminals) or A → a (one terminal). Steps: (1) Remove Λ-productions, (2) Remove unit
productions, (3) Break long productions, (4) Replace terminals in mixed rules.
Step 1 — Find nullable variables (Λ-producers):
• Y → Λ directly ⇒ Y is nullable
• Z → Λ directly ⇒ Z is nullable
• X → XZY Z: if Y, Z nullable then X → X · Λ · Λ · Z = XZ; further analysis: X → Λ
requires X itself to be nullable, but X → a is not nullable, so X is not nullable.
• S → Y b: since Y is nullable, S → b is added.
Step 2 — Remove Λ-productions (add substitution variants):
Y → bY | b | Λ ⇒ Y → bY | b (remove Λ, add b for when Y → Λ)
Z → a (remove Λ production)
S → aXY | aX | Y b | b (added aX for Y → Λ; added b for Y → Λ in Y b)
X → XZY Z | XZZ | XY Z | XZ | a (all combos of removing nullable Y, Z)
Step 3 — Remove unit productions: None remain after above.
Step 4 — Convert to CNF (introduce helper non-terminals for terminals & long
rules):
New non-terminals: Ta → a, Tb → b.
Page 6 of 30
]]
⋆
COS3701: Theoretical Computer Science III
OCT/NOV Examination 2026 Preparation Guide
Covers Past Papers: Oct/Nov 2023 to Oct/Nov 2025
⋆ ⋄ ⋆ ⋄ ⋆ ⋄ ⋆ ⋄ ⋆
[ Computer Science — Automata & Formal Languages [
_ Exam Revision Guide
COS3701
Module Code:
Theoretical Computer Science III
Module Name:
Oct/Nov 2023 & Oct/Nov 2024
Papers Covered:
For Oct/Nov
Predictions:
80 per paper
Total Marks:
2 Hours
Duration:
Study the patterns. Understand the logic. Practise the diagrams.
Exam Revision Notes | COS3701 | 2023–2026
,COS3701 | Exam Revision 2023–2025 Theoretical Computer Science III
PAPER 1 — OCTOBER/NOVEMBER 2024
University Examinations · 05 November 2024 · 80 Marks · 2 Hours
Examiner: DR Mokwana Internal Moderator: Dr TG Moape
Page 2 of 30
,COS3701 | Exam Revision 2023–2025 Theoretical Computer Science III
Question 1 [16 marks]
(a) [2 marks]
Question: 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 bs appear consecutively). Example words: bba, aaabbaaa, aaaabbaaaaaa.
Non-examples: b, a, bab, ab, aaabbbb, abaaabaaaaa.
Answer:
Key Concept
A regular expression describes a regular language using concatenation, union (+),
and Kleene star (∗ ). Key constraint here: exactly one bb, at least one a, no other
adjacent bs.
The language L requires:
• Exactly one occurrence of bb (no bbb, no two separate bb)
• At least one a somewhere in the word
• bs only appear as single b or in the single bb block
Structure: Any b outside the bb block must be isolated (i.e. single). Segments between as
can contain at most one b.
Single-b (non-consecutive) segments over a and b: (a+ b)∗ a∗ (never two consecutive bs).
Let SAFE = a∗ (ba+ )∗ be the pattern of as and isolated bs.
The full expression (one bb block, at least one a):
SAFE · bb · SAFE where at least one a appears in the whole word
Since the bb block itself has no a, the a must come from SAFE. Refined:
RE = a∗ (ba+ )∗ bb a∗ (ba+ )∗ + (a+ (ba+ )∗ )∗ bb a∗ (ba+ )∗
A clean single expression enforcing at least one a overall and exactly one bb:
a∗ (ba+ )∗ bb a+ (ba+ )∗ + a+ (ba+ )∗ bb a∗ (ba+ )∗
Page 3 of 30
,COS3701 | Exam Revision 2023–2025 Theoretical Computer Science III
Both alternatives ensure at least one a is present; the bb block is unique because SAFE never
allows two consecutive bs.
⋆ Exam Tip
Full marks usually require: (1) showing the bb block is isolated, (2) demonstrating at
least one a, and (3) ensuring no extra consecutive bs. Show your reasoning clearly.
(b) [4 marks]
Question: Design a Deterministic Finite Automaton (DFA) that recognises all words in
L as defined above.
Answer:
Key Concept
A DFA has states, transitions on each symbol, one start state, and accept states. Every
input must lead to exactly one transition.
State design strategy:
• Track: (i) whether we have seen a bb, (ii) whether we have seen an a, (iii) how many con-
secutive bs we are currently reading, (iv) dead/trap state for invalid input.
States:
State Meaning
q0 Start: no a seen, no bb seen, no pending b
q1 No a seen, no bb seen, one b pending
q2 a seen, no bb yet, no pending b
q3 a seen, no bb yet, one b pending
q4 a seen (possibly), exactly one bb seen, no trailing b
q5 a seen, one bb seen, one b pending
DEAD Invalid (second bb or bbb)
Accept state: q4 (has seen at least one a and exactly one bb). Note: q5 is not accepting be-
cause a trailing b after bb is only ok if single — we accept when we confirm no more bb.
Key transitions:
a b
• q0 −
→ q2 ; q0 →
− q1
Page 4 of 30
,COS3701 | Exam Revision 2023–2025 Theoretical Computer Science III
b a
− DEAD (would be bb but no a yet);
• q1 → q1 −
→ q2
a b
→ q2 ;
• q2 − q2 →
− q3
b a
− q4 (bb found, a was already seen);
• q3 → q3 −
→ q2
a b
→ q4 ;
• q4 − q4 →
− q5
b a
− DEAD (second bb);
• q5 → q5 −
→ q4
a,b
• DEAD −−→ DEAD
⋆ Exam Tip
Draw the DFA clearly with arrows, label all transitions on each symbol, circle accept
states with double circles. A state diagram earns full marks; a transition table alone
may lose marks.
(c) [4 marks]
Question: Use Theorem 21 to develop a Context-Free Grammar (CFG) for the language
L.
Answer:
Key Concept
Theorem 21 states that every regular language is context-free. A DFA/NFA can be
converted to a CFG: each state qi becomes a non-terminal Qi . For each transition
x
→ qj , add production Qi → x Qj . For each accept state qi , add Qi → Λ.
qi −
Using the DFA above and Theorem 21:
Q0 → a Q2 | b Q1
Q1 → a Q2
Q2 → a Q2 | b Q3 | Λ (if q2 could be accept, but it’s not — remove Λ)
Q3 → b Q4 | a Q2
Q4 → a Q4 | b Q5 | Λ (accept state)
Q5 → a Q4
Note: Q4 is the only accept state, so Q4 → Λ is the only Λ production. The start non-
Page 5 of 30
, COS3701 | Exam Revision 2023–2025 Theoretical Computer Science III
terminal is Q0 .
(d) [6 marks]
Question: Convert the following CFG to Chomsky Normal Form (CNF):
S → aXY | Y b, X → XZY Z | a, Y → bY | Λ, Z→a|Λ
Answer:
Key Concept
Chomsky Normal Form (CNF): All productions are either A → BC (two non-
terminals) or A → a (one terminal). Steps: (1) Remove Λ-productions, (2) Remove unit
productions, (3) Break long productions, (4) Replace terminals in mixed rules.
Step 1 — Find nullable variables (Λ-producers):
• Y → Λ directly ⇒ Y is nullable
• Z → Λ directly ⇒ Z is nullable
• X → XZY Z: if Y, Z nullable then X → X · Λ · Λ · Z = XZ; further analysis: X → Λ
requires X itself to be nullable, but X → a is not nullable, so X is not nullable.
• S → Y b: since Y is nullable, S → b is added.
Step 2 — Remove Λ-productions (add substitution variants):
Y → bY | b | Λ ⇒ Y → bY | b (remove Λ, add b for when Y → Λ)
Z → a (remove Λ production)
S → aXY | aX | Y b | b (added aX for Y → Λ; added b for Y → Λ in Y b)
X → XZY Z | XZZ | XY Z | XZ | a (all combos of removing nullable Y, Z)
Step 3 — Remove unit productions: None remain after above.
Step 4 — Convert to CNF (introduce helper non-terminals for terminals & long
rules):
New non-terminals: Ta → a, Tb → b.
Page 6 of 30
