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

computation-theory, context-free-grammar, context-sensitive-grammar, grammar

Solution

How to write grammar for formal language?

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

Grammar for {an bm | n,m = 0,1,2,..., n <= 2m }

What is you language L = {an bm | 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 an bm, 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 a5 b2 = `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 = {an bm | 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.

Problem

Original source

Related problems

• Tips for creating "Context Free Grammar"