COS3701
Assignment 3
Question 1
Given:
• L1 =(aa)∗
• L2 =(a+b)∗ab(a+b)∗
a) Grammar for L1 :
L1 contains strings formed by zero or more repetitions of "aa".
Grammar G1 =(V,Σ,R,S):
• Σ={a}
• V={S}
• Rules R:
S → aaS | ε
b) Grammar for L2 :
L2 is all strings over {a,b} that contain "ab" as a substring.
Grammar G2 =(V,Σ,R,S):
• Σ={a,b}
• V={S,A,B}
• Rules R:
S → aS | bS | AB
A→a
B → b | bS
Assignment 3
Question 1
Given:
• L1 =(aa)∗
• L2 =(a+b)∗ab(a+b)∗
a) Grammar for L1 :
L1 contains strings formed by zero or more repetitions of "aa".
Grammar G1 =(V,Σ,R,S):
• Σ={a}
• V={S}
• Rules R:
S → aaS | ε
b) Grammar for L2 :
L2 is all strings over {a,b} that contain "ab" as a substring.
Grammar G2 =(V,Σ,R,S):
• Σ={a,b}
• V={S,A,B}
• Rules R:
S → aS | bS | AB
A→a
B → b | bS
