FOR FREE YEAR SOLVED

Please follow examples 1 - 10 in the previous chapter

 

Example 11: 

 

Given language L = Set of all even length string. Construct the corresponding grammar.

 

Solution:

 

This is regular language so, we can write regular expressions for it.

Regular expression: 

 

Grammar of the given language:

 

S → SB | ϵ                                    (This production generates ((a + b) . (a + b))*)

B → AA                                       (This production generates (a + b) (a + b)) 

A → a | b                                      (This production generates (a + b))

 

We can write in more optimize way:

 

 

 

Example 12: 

 

Given language L = Set of all odd length string. Construct the corresponding grammar.

 

Solution:

 

We can also a regular expression: 

 

 

This grammar construction is similar to the previous one Example 11.

 

S → SB | λ                        (This production generates ((a + b).(a + b).(a + b))*)

B → AAA                         (This production generates (a + b) (a + b) (a + b))

A → a | b                          (This production generates (a + b))

 

 

 

Example 13: 

 

Construct grammar for this given language L = anbm | n.m  1

 

Solution:

 

This language is not same as anbn | n  1 because it has an infinite comparison but our given language has no comparison, here anbm both are independent.

 

Regular expression: RE = a+b+, this given language does not contain any empty string because n . m ≥ 1.

 

Grammar:

 

S → AB                            (This final production generates a+b+)

B → bB | b                       (This production generates b+)

A → aA | a                       (This production generates a+)

 

Note:  Every time we are doing the same thing first generates a sub-grammar for sub-string and then merge it to the final production of the grammar. 

 

 

Example 14: 

 

Construct grammar for this given language L = anbncm | n.m  1.

 

Solution:

 

Here we are doing the same thing first derive grammar for anbn then we calculate cm then add them.

And from Example 9 we know the grammar of  anbn | n  1 is  S → aSb | ab.

cm | m  1 is nothing but c+.

 

For the practice we start the grammar as our sub strings then final merge production:

 

 

Now we can rearrange it

 

 

 

Example 15: 

 

Construct grammar for this given language L = ancmbn | n.m  1.

 

Solutions:

 

Firstly we can say it is not regular because it has infinite comparison anbn. Now for this infinite comparison, we can design grammar easily i.e. S → aSb | ab

But there is cm in-between anbn .

 

Still, we first design simple grammar for anbn and cm separately.

 

 

Now how we put c between a and b. Look when we want stop S then we can replace S by aAb.

S → aSb | aAb                 (This production generates an c+ bn)

A → Ac | c                        (This production generates c+)

 

Example: aaaccbbb

 

 

i.e. S → aSb we can use this production no. of time whenever we want to stop it, we use production aAb from where we can get any no. of c’s

 

Note: We cannot S → aSb | A, A → Ac | c because it can generate only c.

 

 

Example 16: 

 

Construct grammar for this given language L = anbncmdm | n.m  1

 

Solutions:

 

This language has two infinite comparisons but not at a time so, it is CFL.

If you see the language properly two comparisons are separated and we know the grammar of  anbn or cmdm from Example 9   i.e. S → aSb | ab.

So, we can construct final grammar very easily by first generating grammar for anbn and then grammar for cmdm then merge two grammars.

 

S → AB                                         (Final production generates anbncmdm)

B → cBd | cd                                 (This production generates cmdm)

A → aAb | ab                                (This production generates anbn)

 

Example 17: 

 

Construct grammar for this given language L = anb2n | n  1.

 

Solutions:

 

This language is CFL because it has only infinite comparison.  It is similar to anbn the only difference is here b is twice of a

And we know the grammar of anbn | n  1 from Example 9   i.e. S → aSb | ab.

 

So, we can construct grammar from the help of the above grammar by adding twice ‘b because here b is twice of a.

 

So, grammar of the given language:

 

S → aSbb | abb          (This production generates anb2n)

 

 

Example 18: 

 

Construct grammar for this given language L = anbmcmdn | n.m  1.

 

Solutions:

 

This given language is almost similar to Example 16 L = anbncmdm | n.m  1

This language has two infinite separate comparisons andn and bmcm

So, first, we design grammar bmcm.

 

A → bAc | bc      (This production generates bmcm)

 

Now as we see from the given language bmcm is in between andn. If any comparison or string is in between a comparison how we design a grammar that we learn from Example 15

 

So, we can design this way 

 

S → aSd | aAd           (This production generates anbncmdm)

 

Overall grammar

 

 

 

Example 19: 

 

Construct grammar for this given language L = am + n bm cn | n.m  0.

 

Solutions:

 

In that case, we first break the power of a and rewrite grammar as  an am bm cn | n.m  0.

 

Now this language pattern is the same as the previous Example 18

 L = anbmcmdn | n.m  1.

 

So, we can design grammar the same as the previous way.

 

S → aSc | aAc                  (This production generates an am bm cn)

A → aAb | ab                   (This production generates am bm)

 

 

 

Example 20: 

 

Construct grammar for this given language L = an bn + m cn | n.m  1

 

Solutions:

 

Same as the previous one we break the power of ‘b’ and rewrite the grammar as an bn bm cm.

 

Now this language similar to the previous one L = anbncmdm | n.m  1 (Example 16)

 

So, we can construct grammar easily as previous was because it has two separated comparison anbn and bmcm.

 

Grammar:

S → AB                                              (This production generates an bn bm cm)

B → bBc | bc                                       (This production generates bmcm)

A → aAb | ab                                      (This production generates anbn)