Grammar to Language Conversion

Grammar to language Conversion:

Language:  

Language is nothing but the generalization of the number of strings accepted by the grammar.

   For Example-  Consider the following grammar G ( {S}, {a}, P, S):

           where p :    S -> aS | a

                        

Number of string accepted by above grammar are -

{a, aa, aaa, aaaa, aaaaa,.........}

Now the language of the above grammar is 

                    L(G) = { aⁿ     |  n>=1}

where L(G) = language of grammar G.

Details: Strings accepted by above grammar are-

  (since S is the starting symbol, so all the strings will be started from S.) 

First string is -           S -> a
Second String is -       S -> aS ->aa       

Third string is -          S -> aS -> aaS -> aaa        
Fourth string is-         S -> aS -> aaS -> aaaS -> aaaa

and so on....

Grammar to Language Conversion:

There are two methods for grammar to language conversion-

 1)  Simple method

 2)  Tree method

Simple method, that is described above by simple example.

Tree method : 

For understanding the tree method, let us take an example-

Consider the following grammar:

                  S -> aSb | ab

the number of strings accepted by tree method are:

and so on...

The accepted by the above grammar using tree method are ( ab, aabb, aaabbb, aaaabbbb....so on)

Now the generalized form  of the grammar (language) is :

                         L(G) = {aⁿ   bⁿ   | n>=1}


Exercises: 

Find out the language corresponding to following grammar using simple method and tree method:

1.     S -> aSb | aAb
        A -> aAb | c

2.     S -> aSbb | abb