Construct grammar given the following language {a^n b^m | n,m = 0,1,2,...,n <= 2m}

Question

I just took my midterm but couldn't answer this question.

Can someone please give a couple of examples of the language and construct a grammar for the language or at least show me how i will go about it?

Also how to write grammar for L:

L = {aⁿ b^m | n,m = 0,1,2,..., n <= 2m } ?

Thanks in advance.

Answer 1

How to write grammar for formal language?

Before read my this answer you should read first: Tips for creating Context free grammars.

Grammar for {aⁿ b^m | n,m = 0,1,2,..., n <= 2m }

What is you language L = {aⁿ b^m | n,m = 0,1,2,..., n <= 2m } description?

Language description: The language L is consist of set of all strings in which symbols a followed by symbols b, where number of symbol b are more than or equals to half of number of a's.

To understand more clearly:

In pattern aⁿ b^m, first symbols a come then symbol b. total number of a 's is n and number of b's is m. The inequality equation says about relation between n and m. To understand the equation:

given:   n <= 2m   
=>       n/2 <= m       means `m` should be = or > then n/2

=>       numberOf(b) >= numberOf(a)/2    ...eq-1

So inequality of n and m says:

numberOf(b) must be more than or equals to half of numberOf(a)

Some example strings in L:

b   numberOf(a)=0 and numberOf(b)=1  this satisfy eq-1        
bb  numberOf(a)=0 and numberOf(b)=2  this satisfy eq-1 
    

So in language string any number of b are possible without a's. (any string of b) because any number is greater then zero (0/2 = 0).

Other examples:

                                     m   n
                                 --------------  
ab     numberOf(a)=1 and numberOf(b)=1 > 1/2   
abb    numberOf(a)=1 and numberOf(b)=2 > 1/2  
abbb   numberOf(a)=1 and numberOf(b)=3 > 1/2  
aabb   numberOf(a)=2 and numberOf(b)=2 > 2/2 = 1  
aaabb  numberOf(a)=3 and numberOf(b)=2 > 3/2 = 1.5
aaaabb numberOf(a)=4 and numberOf(b)=2 = 4/2 = 2  

Points to be note:

• all above strings are possible because number of b's are either equal(=) to half of the number of a or more (>).

• and interesting point to notice is that total a's can also be more then number of b's, but not too much. Whereas number of b's can be more then number of a's by any number of times.

Two more important case are:

• only a as a string not possible.

• note: null ^ string is also allowed because in ^ , numberOf(a) = numberOf(b) = 0 that satisfy equation.

_{At once, it look that writing grammar is tough but really not...}

According to language description, we need following kinds of rules:

rule 1: To generate ^ null string.

 N --> ^  

rule 2: To generate any number of b

 B --> bB | b  

Rule 3: to generate a's:
(1) Remember you can't generate too many a's without generating b's.
(2) Because b's are more then = to half of a's; you need to generate one b for every alternate a
(3) Only a as a string not possible so for first (odd) alternative you need to add b with an a
(4) Whereas for even alternative you can discard to add b (but not compulsory)

So you overall grammar:

   S --> ^ | A | B
   B --> bB | b
   
   A --> aCB | aAB | ^
   C --> aA | ^

here S is start Variable.

In the above grammar rules you may have confusion in A --> aCB | aAB | ^, so below is my explanation:

A --> aCB | aAB | ^   
       ^_____^
       for second alternative a 
        
C --> aA    <== to discard `b`    

and  aAB  to keep b

   

let us we generate some strings in language using this grammar rules, I am writing Left most derivation to avoid explanation.

  ab     S --> A --> aCB --> aB --> ab                        
  abb    S --> A --> aCB --> aB --> abB --> abb
  abbb   S --> A --> aCB --> aB --> abB --> abB --> abbB --> abbb 
  aabb   S --> A --> aAB --> aaABB --> aaBB --> aabB --> aabb
  aaabb  S --> A --> aCB --> aaAB -->  aaaABB --> aaaBB --> aaabB --> aaabb
  aaaabb S --> A --> aCB --> aaAB --> aaaCBB --> aaaaABB --> aaaaBB 
                                                         --> aaaabB 
                                                         --> aaaabb

One more for non-member string:

according to language a⁵ b² = aaaaabb is not possible. because 2 >= 5/2 = 2.5 ==> 2 >= 2.5 inequality fails. So we can't generate this string using grammar too. I try to show below:

In our grammar to generate extra a's we have to use C variable.

S --> A 
  --> aCB 
  --> aaAB 
  --> aa aCB B 
  --> aaa aA BB 
  --> aaaa aCB BB  
           ---              
            ^
           here with first `a` I have to put a `b` too

While my answer is done but I think you can change A's rules like:

A --> aCB | A | ^

Give it a Try!!

EDIT:
_{as @us2012 commented: It would seem to me that then, S -> ^ | ab | aaSb | Sb would be a simpler description. I feel this question would be good for OP and other also.}

OP's language:

L = {aⁿ b^m | n,m = 0,1,2,..., n <= 2m}.

@us2012's Grammar:

S -> ^ | ab | aaSb | Sb    

@us2012's question:

Whether this grammar also generates language L?

Answer is Yes!

The inequality in language between number of a's = n and number of b = m is n =< 2m

We can also understand as:

 n =< 2m
 
 that is 
 
 numberOf(a) = <  twice of numberOf(b) 

And In grammar, when even we add one or two a's we also add one b . So ultimately number of a can't be more then twice of number of b.

Grammar also have rules to generate. any numbers of b's and null ^ strings.

So the simplified Grammar provided by @us2012 is CORRECT and also generates language L exactly.

Notice: The first solution came from derivation as I written in am linked answer, I started with language description then tried to write some basic rules and progressively I could write complete grammar.

Whereas @us2012's answer came by aptitude, you can gain the aptitude to write grammar by reading others' solutions and writing your own for some - just like how you learn programming.