ASSIGNMENT 01
Solution
UNIQUE ASSIGNMENT NUMBER: 712235
Question 1
Chapter 12 – Problem 1 on page 254
Consider the following CFG: S → aS | bb.
Prove that this generates the language defined by the regular expression a∗ bb
1. Observe that the CFG has only one terminal: bb. Thus, words generated by this language
must end with bb. And the shortest possible word is bb.
2. The production aS is right recursive which will expand to:
S ⇒ aS
... ⇒ aaS
... ⇒ aaaS
..
.
... ⇒ aaa ... aaaS
This means that the aS part of the production will generate an arbitrary number of as.
Based on observation 1, it is clear that the CFG can generate words with no as. Based on obser-
vation 2, it is clear that the CFG can generate words with an arbitrary number of as. This is exactly
the language described by a∗ bb which will either generate just the word bb, or all words with an
arbitrary number of as followed by bb.
Based on observations 1 and 2, it is also clear that the CFG cannot generate any other words than
those in the language a∗ bb.
An alternative solution
You will probably remember from COS2601 that the answer to this type of question should consist
of two parts. As soon as the language has been identified, we have to show firstly that the given
grammar only generates words that are in the language (thus no word which is not in the language,
may be generated), and secondly we have to show that every word belonging to the language can
actually be generated by the grammar.
2
Solution
UNIQUE ASSIGNMENT NUMBER: 712235
Question 1
Chapter 12 – Problem 1 on page 254
Consider the following CFG: S → aS | bb.
Prove that this generates the language defined by the regular expression a∗ bb
1. Observe that the CFG has only one terminal: bb. Thus, words generated by this language
must end with bb. And the shortest possible word is bb.
2. The production aS is right recursive which will expand to:
S ⇒ aS
... ⇒ aaS
... ⇒ aaaS
..
.
... ⇒ aaa ... aaaS
This means that the aS part of the production will generate an arbitrary number of as.
Based on observation 1, it is clear that the CFG can generate words with no as. Based on obser-
vation 2, it is clear that the CFG can generate words with an arbitrary number of as. This is exactly
the language described by a∗ bb which will either generate just the word bb, or all words with an
arbitrary number of as followed by bb.
Based on observations 1 and 2, it is also clear that the CFG cannot generate any other words than
those in the language a∗ bb.
An alternative solution
You will probably remember from COS2601 that the answer to this type of question should consist
of two parts. As soon as the language has been identified, we have to show firstly that the given
grammar only generates words that are in the language (thus no word which is not in the language,
may be generated), and secondly we have to show that every word belonging to the language can
actually be generated by the grammar.
2
