COS3701
ASSIGNMENT 3 2025
UNIQUE NO.
DUE DATE: 2025
, COS3701: Theoretical Computer Science III Assignment 3 – 2025
Question 1 [10 Marks]
Given:
L₁ = (aa)*
L₂ = (a + b)ab(a + b)
Grammar for L₁ = (aa)⁎
This language consists of any even number of a's (including ε).
Grammar G₁ = (V, Σ, R, S), where:
V = {S}
Σ = {a}
R:
o S → aaS | ε
Grammar for L₂ = (a + b)ab(a + b):
This language contains strings with at least one occurrence of 'ab'.
Grammar G₂ = (V, Σ, R, S), where:
V = {S, A, B, C}
Σ = {a, b}
R:
o S → aS | bS | A
o A → aB
o B → bC
o C → aC | bC | ε
ASSIGNMENT 3 2025
UNIQUE NO.
DUE DATE: 2025
, COS3701: Theoretical Computer Science III Assignment 3 – 2025
Question 1 [10 Marks]
Given:
L₁ = (aa)*
L₂ = (a + b)ab(a + b)
Grammar for L₁ = (aa)⁎
This language consists of any even number of a's (including ε).
Grammar G₁ = (V, Σ, R, S), where:
V = {S}
Σ = {a}
R:
o S → aaS | ε
Grammar for L₂ = (a + b)ab(a + b):
This language contains strings with at least one occurrence of 'ab'.
Grammar G₂ = (V, Σ, R, S), where:
V = {S, A, B, C}
Σ = {a, b}
R:
o S → aS | bS | A
o A → aB
o B → bC
o C → aC | bC | ε
