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".
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".
