COS3701 Assignment 2 2025 ANSWERS

COS3701
ASSIGNMENT 2 2025

UNIQUE NO.
DUE DATE: 2025

, Question 1 (10 marks): CFG for all words that do not contain the substring "aba"
over Σ = {a, b}

To define a Context-Free Grammar (CFG) that generates all strings over {a, b} that do
not contain the substring aba, we build the grammar based on states tracking recent
letters to avoid aba.

Let’s define the CFG using the following idea:

 Avoid generating “aba”
 Keep track of recent symbols to ensure “aba” is never formed

Let:

 S: start symbol
 A: previous was a
 B: previous was b
 AA: previous was aa
 AB: previous was ab

S → aA | bS | ε
A → aA | bB | ε
B → a (BLOCKED) -- this path would form aba, so OMIT it
| bS | ε

We simplify to a safe grammar:

S → aA | bS | ε
A → aA | bS | ε

Explanation:

 Whenever you see an a, go to A