COS3701
ASSIGNMENT 2 2025
UNIQUE NO.
DUE DATE: 2025
, Question 1: Context-Free Grammar (CFG) for All Strings Without the Substring
"aba"
We are asked to write a CFG that generates all strings over the alphabet {a, b} which
do not contain the substring "aba".
Let’s define the grammar carefully. The idea is to allow all strings over {a, b} while
ensuring we never allow the sequence "a" followed by "b" followed by "a".
Let’s use these variables:
S: Start symbol (generates all valid strings)
A: Last character was a
B: Last character was b
E: Empty string or starting point
Now we construct the grammar:
S → aA | bS | ε
A → aA | bB | ε
B → bS | ε
💡 Explanation:
S can start with a (going to A) or b (continue from S) or end (ε).
A is reached after reading a. From here:
o Another a keeps it safe (still A)
o A b might be dangerous if followed by a, so we shift to B
B means we’ve seen "ab". We must not allow an a after this, so only allow more
bs or end.
ASSIGNMENT 2 2025
UNIQUE NO.
DUE DATE: 2025
, Question 1: Context-Free Grammar (CFG) for All Strings Without the Substring
"aba"
We are asked to write a CFG that generates all strings over the alphabet {a, b} which
do not contain the substring "aba".
Let’s define the grammar carefully. The idea is to allow all strings over {a, b} while
ensuring we never allow the sequence "a" followed by "b" followed by "a".
Let’s use these variables:
S: Start symbol (generates all valid strings)
A: Last character was a
B: Last character was b
E: Empty string or starting point
Now we construct the grammar:
S → aA | bS | ε
A → aA | bB | ε
B → bS | ε
💡 Explanation:
S can start with a (going to A) or b (continue from S) or end (ε).
A is reached after reading a. From here:
o Another a keeps it safe (still A)
o A b might be dangerous if followed by a, so we shift to B
B means we’ve seen "ab". We must not allow an a after this, so only allow more
bs or end.
