Theoretical Computer Science III
COS3701
Assignment 3
School of Computing
This tutorial letter contains important information
about your module.
BARCODE
, Question 1 10
Given that L1 = (aa)* and L2 = (a + b)*ab(a + b)*.
Find grammars for L1 and L2. Then use Theorem 37 to find L1L2.
Solution
For L1 we see that the possible CFG is
S1 ⭢ aaS1 | ᴧ
This can generate zero occurrences of ab or more as required.
For L2 we see that the possible CFG is
S2 ⭢ XabY
X ⭢ aX | bX | ᴧ
Y ⭢ aY | bY | ᴧ
To obtain the required CFG generating L1L2 we apply Theorem 37:
S ⭢S1S2
S1 ⭢ aaS1 | ᴧ
S2 ⭢ XabY
X2 ⭢ aX2 | bX2| ᴧ
Y2 ⭢ aY2 | bY2 | ᴧ
Check that this language generates the required words.
Note that as the two languages given are regular languages one could use the
approach of drawing an FA to recognise each language and then deduce the
CFG for each language from the FA.
Note also that one could use the PDAs for each language to come up with a
combined PDA to recognise L1L2.
To complete this exercise we need to argue/prove that the language generates
the required words.
This proof is typically done in two directions.
1. Prove that the CFG generates all the words in the language.
2. Prove that the CFG generates only the words in the language.
For this example we do the proof as follows:
The CFG generates all the words in the language.
Any word in the language must be of the form (aa)*(a + b)*bb(a + b)*. Let w be
an arbitrary word in the language then w is of the form (aa)x (a + b)yab(a + b)z
where x, y and z are all > 0. The first part of the word can be generated by
repeated applications of the production
S1 ⭢ aaS1 followed by S1 ⭢ ᴧ. The second part of the word comes from
COS3701
Assignment 3
School of Computing
This tutorial letter contains important information
about your module.
BARCODE
, Question 1 10
Given that L1 = (aa)* and L2 = (a + b)*ab(a + b)*.
Find grammars for L1 and L2. Then use Theorem 37 to find L1L2.
Solution
For L1 we see that the possible CFG is
S1 ⭢ aaS1 | ᴧ
This can generate zero occurrences of ab or more as required.
For L2 we see that the possible CFG is
S2 ⭢ XabY
X ⭢ aX | bX | ᴧ
Y ⭢ aY | bY | ᴧ
To obtain the required CFG generating L1L2 we apply Theorem 37:
S ⭢S1S2
S1 ⭢ aaS1 | ᴧ
S2 ⭢ XabY
X2 ⭢ aX2 | bX2| ᴧ
Y2 ⭢ aY2 | bY2 | ᴧ
Check that this language generates the required words.
Note that as the two languages given are regular languages one could use the
approach of drawing an FA to recognise each language and then deduce the
CFG for each language from the FA.
Note also that one could use the PDAs for each language to come up with a
combined PDA to recognise L1L2.
To complete this exercise we need to argue/prove that the language generates
the required words.
This proof is typically done in two directions.
1. Prove that the CFG generates all the words in the language.
2. Prove that the CFG generates only the words in the language.
For this example we do the proof as follows:
The CFG generates all the words in the language.
Any word in the language must be of the form (aa)*(a + b)*bb(a + b)*. Let w be
an arbitrary word in the language then w is of the form (aa)x (a + b)yab(a + b)z
where x, y and z are all > 0. The first part of the word can be generated by
repeated applications of the production
S1 ⭢ aaS1 followed by S1 ⭢ ᴧ. The second part of the word comes from
