COS3701
Assignment 3
Due 21 August 2025
,Question 1
Given that L1 = (aa)∗ and L2 = (a + b)∗ ab(a + b)∗ , find grammars
for L1 and L2 . Then use Theorem 37 to find a grammar for L1 L2 .
The language L1 = (aa)∗ consists of all strings over {a} formed by zero or more repetitions
of the substring ”aa”. Examples include ϵ, aa, aaaa, and so on. Although this is a regular
language, we construct a context-free grammar (CFG) for the purpose of composition with
another CFG.
Grammar for L1 :
Variables: {S1 }
Terminals: {a, b}
Productions:
S1 → aaS1 | ϵ
Start symbol: S1
This grammar generates strings composed only of an even number of a’s. The terminal
b is included in the alphabet for compatibility with L2 , although it does not appear in
L1 ’s productions.
The language L2 = (a + b)∗ ab(a + b)∗ consists of all strings over {a, b} that contain at
least one occurrence of the substring ab. Examples include ab, aab, aba, and baaba.
To construct a CFG for L2 , the required substring ab is made explicit in the middle,
allowing arbitrary strings of a’s and b’s before and after it.
Grammar for L2 :
Variables: {S2 , X}
1
, Terminals: {a, b}
Productions:
S2 → XabX
X → aX | bX | ϵ
Start symbol: S2
This grammar ensures the presence of at least one ab within any derivation, with both
sides allowing arbitrary strings from X.
Theorem 37 states that if L1 and L2 are context-free languages with grammars G1 =
(V1 , Σ, P1 , S1 ) and G2 = (V2 , Σ, P2 , S2 ), and V1 ∩ V2 = ∅, then their concatenation L1 L2
is also context-free. A grammar for L1 L2 can be constructed as follows:
Variables: V = V1 ∪ V2 ∪ {S}
Terminals: {a, b}
Productions:
S → S1 S2
S1 → aaS1 | ϵ
S2 → XabX
X → aX | bX | ϵ
Start symbol: S
To validate the correctness of this grammar, we examine several sample derivations.
Example: “ab”
S → S1 S2 → ϵS2 → XabX → ϵabϵ = ab
2
Assignment 3
Due 21 August 2025
,Question 1
Given that L1 = (aa)∗ and L2 = (a + b)∗ ab(a + b)∗ , find grammars
for L1 and L2 . Then use Theorem 37 to find a grammar for L1 L2 .
The language L1 = (aa)∗ consists of all strings over {a} formed by zero or more repetitions
of the substring ”aa”. Examples include ϵ, aa, aaaa, and so on. Although this is a regular
language, we construct a context-free grammar (CFG) for the purpose of composition with
another CFG.
Grammar for L1 :
Variables: {S1 }
Terminals: {a, b}
Productions:
S1 → aaS1 | ϵ
Start symbol: S1
This grammar generates strings composed only of an even number of a’s. The terminal
b is included in the alphabet for compatibility with L2 , although it does not appear in
L1 ’s productions.
The language L2 = (a + b)∗ ab(a + b)∗ consists of all strings over {a, b} that contain at
least one occurrence of the substring ab. Examples include ab, aab, aba, and baaba.
To construct a CFG for L2 , the required substring ab is made explicit in the middle,
allowing arbitrary strings of a’s and b’s before and after it.
Grammar for L2 :
Variables: {S2 , X}
1
, Terminals: {a, b}
Productions:
S2 → XabX
X → aX | bX | ϵ
Start symbol: S2
This grammar ensures the presence of at least one ab within any derivation, with both
sides allowing arbitrary strings from X.
Theorem 37 states that if L1 and L2 are context-free languages with grammars G1 =
(V1 , Σ, P1 , S1 ) and G2 = (V2 , Σ, P2 , S2 ), and V1 ∩ V2 = ∅, then their concatenation L1 L2
is also context-free. A grammar for L1 L2 can be constructed as follows:
Variables: V = V1 ∪ V2 ∪ {S}
Terminals: {a, b}
Productions:
S → S1 S2
S1 → aaS1 | ϵ
S2 → XabX
X → aX | bX | ϵ
Start symbol: S
To validate the correctness of this grammar, we examine several sample derivations.
Example: “ab”
S → S1 S2 → ϵS2 → XabX → ϵabϵ = ab
2
