COS3701
Assignment 3
2025
, Question 1 [10 Marks]
Let:
L1=(aa)∗L_1 = (aa)^*L1=(aa)∗
L2=(a+b)∗ab(a+b)∗L_2 = (a + b)^*ab(a + b)^*L2=(a+b)∗ab(a+b)∗
Grammar for L1L_1L1:
We want strings of even number of a’s.
Grammar G1:
less
CopyEdit
S → AA | ε
A → aa
Grammar for L2L_2L2:
Strings containing “ab” as a substring.
Grammar G2:
vbnet
CopyEdit
S → XabY
X → aX | bX | ε
Y → aY | bY | ε
To find L1L2L_1L_2L1L2:
Apply Theorem 37:
Assignment 3
2025
, Question 1 [10 Marks]
Let:
L1=(aa)∗L_1 = (aa)^*L1=(aa)∗
L2=(a+b)∗ab(a+b)∗L_2 = (a + b)^*ab(a + b)^*L2=(a+b)∗ab(a+b)∗
Grammar for L1L_1L1:
We want strings of even number of a’s.
Grammar G1:
less
CopyEdit
S → AA | ε
A → aa
Grammar for L2L_2L2:
Strings containing “ab” as a substring.
Grammar G2:
vbnet
CopyEdit
S → XabY
X → aX | bX | ε
Y → aY | bY | ε
To find L1L2L_1L_2L1L2:
Apply Theorem 37:
