COS3701
Assignment 2 2025
, Question 1
Answer
Construct a context-free grammar (CFG) that generates all strings composed of the
symbols {a,b}}, but excludes any string that contains the substring "aba".
This means:
✓ "aba", "caba", "ababa", "aabaa" → Invalid
✓ "", "a", "b", "aa", "bb", "abb", "bab", "baab", etc. → Valid
Defination of three productive states and one blocking state:
• S: Start state (no partial match)
• A: Last character was ‘a’
• AB: Last characters were ‘a’ then ‘b’
• BLOCK: Trap state, entered on detecting "aba"
CFG Components
Terminals:
Σ= {a, b}}
Nonterminals:
{S, A, AB, BLOCK}
Start Symbol:
S
Productions:
S → aA ∣ bS ∣ ε
Assignment 2 2025
, Question 1
Answer
Construct a context-free grammar (CFG) that generates all strings composed of the
symbols {a,b}}, but excludes any string that contains the substring "aba".
This means:
✓ "aba", "caba", "ababa", "aabaa" → Invalid
✓ "", "a", "b", "aa", "bb", "abb", "bab", "baab", etc. → Valid
Defination of three productive states and one blocking state:
• S: Start state (no partial match)
• A: Last character was ‘a’
• AB: Last characters were ‘a’ then ‘b’
• BLOCK: Trap state, entered on detecting "aba"
CFG Components
Terminals:
Σ= {a, b}}
Nonterminals:
{S, A, AB, BLOCK}
Start Symbol:
S
Productions:
S → aA ∣ bS ∣ ε
