COS3701
ASSIGNMENT 3 2025
UNIQUE NO.
DUE DATE: 2025
, Question 1 [10 Marks]
You are given two languages:
L1 = (aa)*
This means strings with zero or more repetitions of “aa”. Examples include: ε
(empty string), aa, aaaa, aaaaaa, etc.
L2 = (a + b)*ab(a + b)*
This language includes all strings that contain the substring "ab" somewhere in
the middle, surrounded by any number of a’s and b’s on either side.
Grammar for L1:
We need to create a grammar G1 = (V, Σ, R, S) that generates only strings in (aa)*
Variables (V): {S}
Alphabet (Σ): {a}
Rules (R):
o S → aaS
o S→ε
Start symbol: S
Explanation: This grammar repeatedly adds “aa” or stops with ε.
Grammar for L2:
We need to create a grammar G2 = (V, Σ, R, S) that generates strings with “ab” in the
middle.
Variables (V): {S, A, B}
Alphabet (Σ): {a, b}
Rules (R):
ASSIGNMENT 3 2025
UNIQUE NO.
DUE DATE: 2025
, Question 1 [10 Marks]
You are given two languages:
L1 = (aa)*
This means strings with zero or more repetitions of “aa”. Examples include: ε
(empty string), aa, aaaa, aaaaaa, etc.
L2 = (a + b)*ab(a + b)*
This language includes all strings that contain the substring "ab" somewhere in
the middle, surrounded by any number of a’s and b’s on either side.
Grammar for L1:
We need to create a grammar G1 = (V, Σ, R, S) that generates only strings in (aa)*
Variables (V): {S}
Alphabet (Σ): {a}
Rules (R):
o S → aaS
o S→ε
Start symbol: S
Explanation: This grammar repeatedly adds “aa” or stops with ε.
Grammar for L2:
We need to create a grammar G2 = (V, Σ, R, S) that generates strings with “ab” in the
middle.
Variables (V): {S, A, B}
Alphabet (Σ): {a, b}
Rules (R):
