CODEWITHSUNDEEP
context-free-grammarformal-languagesautomata-theory
Satya
Satya

Reputation: 11

Finding Context Free grammar (CFG)

Give a context free grammar H that generates the language

 M = {a^m
b^n
| 2m > n > m}.
‘

Hint: m can’t be 0, because in that case 2m = m. m can’t be 1, because in that case 2 > n > 1, such a natural number n doesn’t exist. So the shortest string in the language M is aabbb. For longer strings, you need to make sure that the number n of bs and the number m of as satisfy 2m > n > m.

Upvotes: 1

Views: 980

Answers (1)

Patrick87
Patrick87

Reputation: 28292

We know aabbb is in the language, so S -> aabbb isn't a bad start. How do we get longer strings in the language? Well, we need to keep 2m > n > m. The shortest strings (for a given number of as) in this language have one more b than they have a, so we might guess that S -> aSb is not a bad guess; it certainly generates strings in our language, namely, the shortest ones (for a given number of as). Similarly, the longest strings in our language have one fewer b than twice as many a as they have, so S -> aSbb is also safe in that it generates the longest strings (for a given number of as). Our grammar so far is this:

S -> aabbb
S -> aSb
S -> aSbb

Every production after the first adds a single a and either one or two bs. The second production can be used alone to generate the shortest strings (for a given number of as) and the third, when used alone, generates the longest ones (for a given number of as). What about the strings in between the shortest and longest ones? Can these productions be used to get all of those strings too?

They can. You can prove it by induction. You have to show that all strings of length n (1) in the language are generated by the grammar and (2) generated by the grammar are in the language.

Base case: the shortest string in the language is aabbb and it is generated by the grammar.

Induction hypothesis: assume the grammar generates all and only strings in the language for any string up to and including length k.

Induction step: we must show the grammar generates all and only strings in the language for any string of length k + 1. We have already argued that the grammar cannot produce a string not in the language; by using the second production only, you get n = m + 1, and by using the third production only you get n = 2m - 1. To see that it generates all strings in the language, recall that any string in the language starts with at least two as and ends with at least three bs. So, it can be written as aaxbbb. It can be shown that if this string is in the language, then one or both of axbb and/or axb must also be in the language.

  1. axbb is in L if 2(m - 1) > n - 1 > m - 1, or 2m - 1 > n > m
  2. axb is in L if 2(m - 1) > n - 2 > m - 1, or 2m > n > m + 1.

Since in every case starting with the base case we have at least one of 2m - 1 > n and/or n > m + 1, one of those is also in L. By the induction hypothesis, the grammar generates it; and one of the grammar's productions will produce from it the original string of length k + 1. So the grammar generates all strings in L.

Upvotes: 1

Related Questions