COS3701 ASSIGNMENT 1 YEARLY MODULE 2022 [Unique No.: 563429]

COS3701


ASSIGNMENT 1


2022 YEARLY MODULE


Unique Number: 563429

, ASSIGNMENT 01
Solution
563429
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

, COS3701/201


Consider again the given CFG:

S → aS|bb



and the regular expression


a∗ bb


Let us call the language generated by the regular expression L.


• First we have to show that all words generated by the given grammar are words in L: The
first production, namely S → aS, introduces the nonterminal S into the expression on the
righthand side. We can apply the production S → aS any number of times (including zero
times) to generate the a∗ part of L. At some point S will have to be replaced by terminals.
The other production S → bb is the only production which can terminate the working string.
Thus we see that all words which are generated must end in bb and only one bb-substring is
possible. Thus it is the case that the given grammar only generates words in L.

• Secondly we have to show that all words in L can be generated by the grammar. Let us
choose any word in L and call this word w. w must be of the form y1 bb for some y1 where y1 is
some string of as or no as at all. The y1 part of w can be generated by repeated applications
of the production S → aS. The production S → bb is the only production which can be
applied to terminate the working string with. To generate the word bb only the production
S → bb is applied once. Thus w can be generated by the grammar. As w is an arbitrary
word. Then we have that the grammar can generate any word in L.




Question 2


Chapter 12 –Problem 8(ii) on page 256

Find a CFG for the following language over the alphabet Σ = {a b}.

The language of all words that have exactly two or three b’s.

We begin by constructing an FA that will accept the language in question, and then we construct
the CFG by applying the construction algorithm from theorem 21.

We now label the states, which allows us to construct the CFG without much trouble.

From here, we can construct the CFG using the algorithm provided in theorem 21.


3