COS3701 Assignment 2 (COMPLETE ANSWERS) 2025

COS3701
ASSIGNMENT 2 2025

UNIQUE NO.
DUE DATE: 2025

, Theoretical Computer Science III

Question 1 [10 marks]

Find CFGs for all words that do not have the substring "aba" over the alphabet ∑
= {a, b}.

To generate all strings not containing "aba", construct a CFG that keeps track of
recent characters and avoids transitions leading to "aba".

Let:

 S = start symbol
 A = last character was a
 AA = last two characters were aa (we're avoiding "aba")
 B = last character was b

CFG:

S → aA | bS | ε
A → aA | bB
B → aAA | bS | ε
AA → aAA | bB

Explanation:

 S begins the string and avoids directly producing "aba".
 A remembers a single a, AA remembers two as.
 B continues from a b, carefully checking that we don't reach "aba".