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
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through EFT, credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying this summary from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller CheggAcademy. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy this summary for R100,00. You're not tied to anything after your purchase.
