COS3701 Assignment 2 Memo | Due July 2025

, PLEASE USE THIS DOCUMENT AS A GUIDE TO ANSWER YOUR ASSIGNMENT

 Question 1

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

Step-by-step Idea
Define non-terminal symbols that track the recent history of characters so prevent "aba" from
forming.

Define the grammar in a way that ensures:
 Don’t produce the exact sequence "aba".
 Do allow any combination of as and bs except the one that introduces "aba".

Grammar Overview
Define non-terminals:

 S — the start symbol, generates all safe strings.
 A — last character was a
 B — last character was b
 AA — last two characters were aa
 AB — last two characters were ab (danger zone — can't allow an a next!)
 avoid allowing transitions that would complete the forbidden "aba".

CFG Rules
 S → aA | bB | ε // Start with a or b, or empty string
 A → aAA | bB // 'a' followed by something, or safe 'b'
 AA → aAA | bB // 'aa...' — okay as long as not followed by 'ba'
 B → aA | bB // 'b' followed by anything safe
 AB → bB // After 'ab' only 'b' is allowed (not 'a')

Final CFG
Define non-terminals:

 S – any valid string
 X – the string ends in a
 Y – the string ends in ab

Rules:
 S → aX | bS | ε // Start with a or b, or end (empty string)
 X → aX | bY // After an 'a', if 'b' follows, we go to Y
 Y → bS // From 'ab', only a 'b' is allowed next