⋆ ⋆ ⋆
]]
COS2601: Theoretical Computer Science II
OCT/NOV Examination 2026 — Covering Papers from 2023 to 2025
⋆ ⋄ ⋆ ⋄ ⋆ ⋄ ⋆ ⋄ ⋆
Computer Science — Formal Languages & Automata Theory
B Exam Revision Guide
COS2601
Module Code:
Theoretical Computer Science II
Module Name:
OCT/NOV 2023, 2024 & 2025
Papers Covered:
OCT/NOV 2026
Target Year:
100 marks (typical)
Total Marks:
2 hours
Duration:
Master the theory. Build the automata. Prove the pumping. Pass the exam.
⋆ Exam Revision Notes | COS2601 | 2026 ⋆
,COS2601 | Exam Revision 2026 Theoretical Computer Science II
— OCT/NOV 2025 EXAMINATION PAPER —
Question 1 [10 marks]
Question: (a) Let S = {a, ab, ba, abb}. For each of the following strings, determine
whether it belongs to S ∗ :
(i) aababba (2)
(ii) abbaabb (2)
(b) Give an example of two sets S and T of strings over Σ = {a, b} such that S ̸= T , but
S ∗ = T ∗ . Justify your answer. (4)
(c) Explain what is meant by the term concatenation of two languages L1 and L2 , and
give an example where |L1 | = 2 and |L2 | = 2. (2)
Answer:
(a)(i) Is aababba ∈ S ∗ ?
We attempt to decompose aababba using words from S = {a, ab, ba, abb}:
aababba = a + ab + abb + a ⇒ a · ab · abb · a
Check: a ∈ S, ab ∈ S, abb ∈ S, a ∈ S. Concatenation: a ab abb a = aababba. Yes, aababba ∈
S∗.
(a)(ii) Is abbaabb ∈ S ∗ ?
Attempt: abb + a + abb = abbaaabb (length 8, too long). Try: ab + ba + abb = abbaabb (length
7). Check: ab ∈ S, ba ∈ S, abb ∈ S. Yes, abbaabb ∈ S ∗ .
(b)
Let S = {a} and T = {a, aa}.
• S ̸= T (clearly, since aa ∈ T but aa ∈
/ S).
• S ∗ = {ε, a, aa, aaa, . . .} = a∗ .
• T ∗ : since a ∈ T , T ∗ also contains all concatenations of a’s, so T ∗ = a∗ .
• Therefore S ∗ = T ∗ , even though S ̸= T .
Page 2 of 31 ⋆
,COS2601 | Exam Revision 2026 Theoretical Computer Science II
Exam Tip
For S ∗ = T ∗ to hold with S ̸= T , the extra word in T must already be expressible as a
concatenation of words from S. Here aa = a · a, so adding aa to S changes the set but
not the Kleene closure.
(c)
The concatenation of two languages L1 and L2 is:
L1 L2 = {xy | x ∈ L1 and y ∈ L2 }
Every word from L1 is followed by every word from L2 .
Example
Let L1 = {a, ab} and L2 = {b, ba}.
Then L1 L2 = {ab, aba, abb, abba}.
Page 3 of 31 ⋆
,COS2601 | Exam Revision 2026 Theoretical Computer Science II
Question 2 [10 marks]
Question: (a) Consider the regular expression r = (a + b)∗ abb (a + b)∗ . Does r define
the language of all words over {a, b} that contain the substring abb? Justify your answer
with a counter-example if not, or a proof sketch if yes. (4)
(b) Write a regular expression for the language over Σ = {0, 1} consisting of all binary
strings that begin with 00 and end with 11. (3)
(c) Write a regular expression for the language over Σ = {a, b} of all words that contain
neither the substring aa nor the substring bb. (3)
Answer:
(a)
Yes, r = (a + b)∗ abb (a + b)∗ defines exactly the set of all words over {a, b} containing abb as a
substring.
• Forward direction: Any word generated by r has the form w1 abb w2 where w1 , w2 ∈
{a, b}∗ . It clearly contains abb.
• Reverse direction: If a word w contains abb, write w = w1 abb w2 . Then w1 ∈ (a + b)∗
and w2 ∈ (a + b)∗ , so w is generated by r.
The regular expression is correct.
(b)
Language: all binary strings starting with 00 and ending with 11.
r = 00 (0 + 1)∗ 11 + 0011
The + 0011 handles the case where the string is exactly 0011 (no middle). However, since
00 (0 + 1)∗ 11 already accepts 0011 (where (0 + 1)∗ = ε), the simpler form is:
r = 00 (0 + 1)∗ 11
Watch Out
The string 0011 must be accepted. Check: (0 + 1)∗ = ε is allowed, so 00 ε 11 = 0011. It
works.
(c)
Page 4 of 31 ⋆
,COS2601 | Exam Revision 2026 Theoretical Computer Science II
Words over {a, b} with no aa and no bb must alternate letters, possibly starting with a or b:
r = ε + a + b + (ab)∗ + a(ba)∗ + b(ab)∗ + (ba)∗
A cleaner formulation: every consecutive pair must differ, so the language is {(ab)n , (ba)n , a(ba)n , b(ab)n |
n ≥ 0}:
r = (ab)∗ (ε + a) + (ba)∗ (ε + b)
Exam Tip
Verify by checking: abab accepted (yes, (ab)2 ); aab rejected (contains aa, not in r); bba
rejected (contains bb, not in r).
Page 5 of 31 ⋆
, COS2601 | Exam Revision 2026 Theoretical Computer Science II
Question 3 [20 marks]
(a) [10 marks]
Question: Build a Finite Automaton (FA) that accepts the language L over
Σ = {a, b} consisting of all words that start with ab and end with ba. Words of length
less than 4 that are exactly abba should also be accepted.
Answer:
Key Concept
Design strategy: Track the prefix ab using states 1–2. Once ab is read, track the most
recent characters to detect the suffix ba. The word abba must also be accepted.
States: q0 (start), q1 (read a), q2 (read ab), q3 (in middle, last char ̸= b), q4 (last char is b), q5
(read ba – final), qdead (trap).
b a b
a a b a b a
q0 q1 q2 q3 q4 q5
b
b a
qd
a, b
• q0 : start state.
• q1 : exactly one a read so far.
• q2 : prefix ab confirmed; tracking for suffix.
• q3 : in middle; last character read was a.
• q4 : last character read was b (potential start of suffix ba).
• q5 : accepting – ended on ba.
• qd : dead/trap state (no ab prefix).
Page 6 of 31 ⋆
]]
COS2601: Theoretical Computer Science II
OCT/NOV Examination 2026 — Covering Papers from 2023 to 2025
⋆ ⋄ ⋆ ⋄ ⋆ ⋄ ⋆ ⋄ ⋆
Computer Science — Formal Languages & Automata Theory
B Exam Revision Guide
COS2601
Module Code:
Theoretical Computer Science II
Module Name:
OCT/NOV 2023, 2024 & 2025
Papers Covered:
OCT/NOV 2026
Target Year:
100 marks (typical)
Total Marks:
2 hours
Duration:
Master the theory. Build the automata. Prove the pumping. Pass the exam.
⋆ Exam Revision Notes | COS2601 | 2026 ⋆
,COS2601 | Exam Revision 2026 Theoretical Computer Science II
— OCT/NOV 2025 EXAMINATION PAPER —
Question 1 [10 marks]
Question: (a) Let S = {a, ab, ba, abb}. For each of the following strings, determine
whether it belongs to S ∗ :
(i) aababba (2)
(ii) abbaabb (2)
(b) Give an example of two sets S and T of strings over Σ = {a, b} such that S ̸= T , but
S ∗ = T ∗ . Justify your answer. (4)
(c) Explain what is meant by the term concatenation of two languages L1 and L2 , and
give an example where |L1 | = 2 and |L2 | = 2. (2)
Answer:
(a)(i) Is aababba ∈ S ∗ ?
We attempt to decompose aababba using words from S = {a, ab, ba, abb}:
aababba = a + ab + abb + a ⇒ a · ab · abb · a
Check: a ∈ S, ab ∈ S, abb ∈ S, a ∈ S. Concatenation: a ab abb a = aababba. Yes, aababba ∈
S∗.
(a)(ii) Is abbaabb ∈ S ∗ ?
Attempt: abb + a + abb = abbaaabb (length 8, too long). Try: ab + ba + abb = abbaabb (length
7). Check: ab ∈ S, ba ∈ S, abb ∈ S. Yes, abbaabb ∈ S ∗ .
(b)
Let S = {a} and T = {a, aa}.
• S ̸= T (clearly, since aa ∈ T but aa ∈
/ S).
• S ∗ = {ε, a, aa, aaa, . . .} = a∗ .
• T ∗ : since a ∈ T , T ∗ also contains all concatenations of a’s, so T ∗ = a∗ .
• Therefore S ∗ = T ∗ , even though S ̸= T .
Page 2 of 31 ⋆
,COS2601 | Exam Revision 2026 Theoretical Computer Science II
Exam Tip
For S ∗ = T ∗ to hold with S ̸= T , the extra word in T must already be expressible as a
concatenation of words from S. Here aa = a · a, so adding aa to S changes the set but
not the Kleene closure.
(c)
The concatenation of two languages L1 and L2 is:
L1 L2 = {xy | x ∈ L1 and y ∈ L2 }
Every word from L1 is followed by every word from L2 .
Example
Let L1 = {a, ab} and L2 = {b, ba}.
Then L1 L2 = {ab, aba, abb, abba}.
Page 3 of 31 ⋆
,COS2601 | Exam Revision 2026 Theoretical Computer Science II
Question 2 [10 marks]
Question: (a) Consider the regular expression r = (a + b)∗ abb (a + b)∗ . Does r define
the language of all words over {a, b} that contain the substring abb? Justify your answer
with a counter-example if not, or a proof sketch if yes. (4)
(b) Write a regular expression for the language over Σ = {0, 1} consisting of all binary
strings that begin with 00 and end with 11. (3)
(c) Write a regular expression for the language over Σ = {a, b} of all words that contain
neither the substring aa nor the substring bb. (3)
Answer:
(a)
Yes, r = (a + b)∗ abb (a + b)∗ defines exactly the set of all words over {a, b} containing abb as a
substring.
• Forward direction: Any word generated by r has the form w1 abb w2 where w1 , w2 ∈
{a, b}∗ . It clearly contains abb.
• Reverse direction: If a word w contains abb, write w = w1 abb w2 . Then w1 ∈ (a + b)∗
and w2 ∈ (a + b)∗ , so w is generated by r.
The regular expression is correct.
(b)
Language: all binary strings starting with 00 and ending with 11.
r = 00 (0 + 1)∗ 11 + 0011
The + 0011 handles the case where the string is exactly 0011 (no middle). However, since
00 (0 + 1)∗ 11 already accepts 0011 (where (0 + 1)∗ = ε), the simpler form is:
r = 00 (0 + 1)∗ 11
Watch Out
The string 0011 must be accepted. Check: (0 + 1)∗ = ε is allowed, so 00 ε 11 = 0011. It
works.
(c)
Page 4 of 31 ⋆
,COS2601 | Exam Revision 2026 Theoretical Computer Science II
Words over {a, b} with no aa and no bb must alternate letters, possibly starting with a or b:
r = ε + a + b + (ab)∗ + a(ba)∗ + b(ab)∗ + (ba)∗
A cleaner formulation: every consecutive pair must differ, so the language is {(ab)n , (ba)n , a(ba)n , b(ab)n |
n ≥ 0}:
r = (ab)∗ (ε + a) + (ba)∗ (ε + b)
Exam Tip
Verify by checking: abab accepted (yes, (ab)2 ); aab rejected (contains aa, not in r); bba
rejected (contains bb, not in r).
Page 5 of 31 ⋆
, COS2601 | Exam Revision 2026 Theoretical Computer Science II
Question 3 [20 marks]
(a) [10 marks]
Question: Build a Finite Automaton (FA) that accepts the language L over
Σ = {a, b} consisting of all words that start with ab and end with ba. Words of length
less than 4 that are exactly abba should also be accepted.
Answer:
Key Concept
Design strategy: Track the prefix ab using states 1–2. Once ab is read, track the most
recent characters to detect the suffix ba. The word abba must also be accepted.
States: q0 (start), q1 (read a), q2 (read ab), q3 (in middle, last char ̸= b), q4 (last char is b), q5
(read ba – final), qdead (trap).
b a b
a a b a b a
q0 q1 q2 q3 q4 q5
b
b a
qd
a, b
• q0 : start state.
• q1 : exactly one a read so far.
• q2 : prefix ab confirmed; tracking for suffix.
• q3 : in middle; last character read was a.
• q4 : last character read was b (potential start of suffix ba).
• q5 : accepting – ended on ba.
• qd : dead/trap state (no ab prefix).
Page 6 of 31 ⋆
