Question

Give CFG for the following languages,

a. anbm where m = n-1 and n = 1,2,3…
Some words belonging to this language are, a , aab , aaabb , aaaabbb , ….
b. anb2n where n = 1,2,3…
Some words belonging to this language are, abb , aabbbb , aaabbbbbb , ….

Answer 1

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.