COS3701 Assignment 2 2025 (Exceptional Response) Due July 2025

COS3701
Assignment 2
Due July 2025

, COS3701

Assignment 2

Due July 2025



Question 1: Constructing Context-Free Grammars (CFGs) for Words Without
Substring "aba" Over Alphabet Σ = {a, b}

Problem Statement

Construct context-free grammars (CFGs) for all words over the alphabet Σ = {a, b}
that do not contain the substring "aba".

Analysis and Approach

A context-free grammar generates a language by defining production rules that
describe valid strings. The language in question consists of all strings over Σ = {a,
b} that do not contain "aba" as a substring. This is a regular language, as it can
be recognized by a finite automaton that avoids transitions leading to "aba".
However, since the task requires a CFG, we must design production rules that
ensure no derivation produces "aba".

To avoid "aba", we control sequences where an "a" is followed by a "b" and then
another "a". We can use a finite automaton to model the language and then
convert it to a CFG, or construct a CFG directly by preventing "aba" formation.

Solution

Define nonterminals generating:

• Strings starting with "a" avoiding "aba".

• Strings starting with "b" avoiding "aba".

• The empty string ε.