Question

Give CFG for the following languages,

Answer 1

Answer:

a.  

CFG for {$a^{n}$$b^{m}$, m=n-1 and n=1,2,3… …}

Here we can have a string containing only a single a and no b.

For that the production rule is S → aT, T → ε

Now  to get the strings with at least one b, the production rule is to be

T → ATB/ ε

A → a

B → b

Now merging two set of production rules:

S → aT

T → ATB/ε    [As T → ε is in both set, so one occurrence is taken]

A → a

B → b

Now let us generate “aaabb”

S → aT → a ATB → aAATBB → aaATBB → aaaTBB → aaaεBB → aaaεbB →aaaεbb → aaabb

b.  

CFG for {$a^{n}$$b^{2n}$, n=1,2,3… …}

Here for every single a, we have to generate two b’s.

So the production rule is to be:

                          S → aSbb/ε

Each time S will generate two b’s for one a.