, PLEASE USE THIS DOCUMENT AS A GUIDE TO ANSWER YOUR ASSIGNMENT
Question 1
1. Given that L1 = (aa)* and L2 = (a + b)*ab(a + b)*. Find grammars for L1 and L2. Then use
Theorem 37 to find L1L2.
Step 1: Find grammars for L1 and L 2
For L1 - (aa)* :
The language L1 consists of strings made up of zero or more repetitions of the string "aa". The grammar for
L 1 can be expressed as:
Here, 81 is the start symbol, which can produce the string "aa" followed by another instance of S1 , or it can
produce the empty string€, allowing for zero repetitions of "aa".
For L2 - (a + b)*ab(a + b)*:
The language L2 consists of strings over the alphabet { a, b} that include an "ab" somewhere in the string.
The grammar for L2 can be expressed as:
• X -t ax I bX I €
• Y -+ aY I bY I1:
Here, 82 is the start symbol, and it generates a string where X represents any sequence of "a"s and "b"s
before "ab", and Y represents any sequence of "a"s and "b"s after "ab".
Question 1
1. Given that L1 = (aa)* and L2 = (a + b)*ab(a + b)*. Find grammars for L1 and L2. Then use
Theorem 37 to find L1L2.
Step 1: Find grammars for L1 and L 2
For L1 - (aa)* :
The language L1 consists of strings made up of zero or more repetitions of the string "aa". The grammar for
L 1 can be expressed as:
Here, 81 is the start symbol, which can produce the string "aa" followed by another instance of S1 , or it can
produce the empty string€, allowing for zero repetitions of "aa".
For L2 - (a + b)*ab(a + b)*:
The language L2 consists of strings over the alphabet { a, b} that include an "ab" somewhere in the string.
The grammar for L2 can be expressed as:
• X -t ax I bX I €
• Y -+ aY I bY I1:
Here, 82 is the start symbol, and it generates a string where X represents any sequence of "a"s and "b"s
before "ab", and Y represents any sequence of "a"s and "b"s after "ab".
