COS3701
Assignment 3
(COMPLETE
ANSWERS) 2025
FOR ASSISTANCE CONTACT:
100% TRUSTED WORKINGS, EXPLANATIONS &
SOLUTIONS
, COS3701 Assignment 3
(COMPLETE ANSWERS) 2025
Question 1 [10] Given that L1 = (aa)* and L2 = (a +
b)*ab(a + b)*. Find grammars for L1 and L2. Then use
Theorem 37 to find L1L2.
To answer Question 1 [10 marks], we will:
1. Define grammars for L1 and L2
2. Apply Theorem 37 to find L1L2
🧩 Step 1: Define Grammars for L1 and L2
🔷 Language L1 = (aa)*
This language consists of even numbers of a, because each repetition adds two
as.
Grammar G1 for L1:
Let G1 = (V1, Σ1, R1, S1), where:
V1 = {S1}
Σ1 = {a}
R1:
o S1 → aaS1 | ε
This generates strings like: ε, aa, aaaa, aaaaaa, etc.
🔷 Language L2 = (a + b)*ab(a + b)*
This is the set of all strings over a and b that contain 'ab' as a substring.
Grammar G2 for L2:
Let G2 = (V2, Σ2, R2, S2), where:
V2 = {S2, A, B}
Assignment 3
(COMPLETE
ANSWERS) 2025
FOR ASSISTANCE CONTACT:
100% TRUSTED WORKINGS, EXPLANATIONS &
SOLUTIONS
, COS3701 Assignment 3
(COMPLETE ANSWERS) 2025
Question 1 [10] Given that L1 = (aa)* and L2 = (a +
b)*ab(a + b)*. Find grammars for L1 and L2. Then use
Theorem 37 to find L1L2.
To answer Question 1 [10 marks], we will:
1. Define grammars for L1 and L2
2. Apply Theorem 37 to find L1L2
🧩 Step 1: Define Grammars for L1 and L2
🔷 Language L1 = (aa)*
This language consists of even numbers of a, because each repetition adds two
as.
Grammar G1 for L1:
Let G1 = (V1, Σ1, R1, S1), where:
V1 = {S1}
Σ1 = {a}
R1:
o S1 → aaS1 | ε
This generates strings like: ε, aa, aaaa, aaaaaa, etc.
🔷 Language L2 = (a + b)*ab(a + b)*
This is the set of all strings over a and b that contain 'ab' as a substring.
Grammar G2 for L2:
Let G2 = (V2, Σ2, R2, S2), where:
V2 = {S2, A, B}
