COS3701
ASSIGNMENT 3 2025
UNIQUE NO.
DUE DATE: 2025
, Theoretical Computer Science III
Question 1
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 | ε
This grammar generates (a + b)ab(a + b).
ASSIGNMENT 3 2025
UNIQUE NO.
DUE DATE: 2025
, Theoretical Computer Science III
Question 1
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 | ε
This grammar generates (a + b)ab(a + b).
