, 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
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
