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 $\mathbf{L}\mathbf{ }\mathbf{=}\mathbf{ }{\mathbf{a}}^{\mathbf{n}}{\mathbf{b}}^{\mathbf{m}}\mathbf{ }\mathbf{|}\mathbf{ }\mathbf{n}\mathbf{.}\mathbf{m}\mathbf{ }\mathbf{\ge }\mathbf{ }\mathbf{1}$. 

Solution:

This language is not same as ${\mathbf{a}}^{\mathbf{n}}{\mathbf{b}}^{\mathbf{n}}\mathbf{ }\mathbf{|}\mathbf{ }\mathbf{n}\mathbf{ }\mathbf{\ge }\mathbf{ }\mathbf{1}$ because it has an infinite comparison but our given language has no comparison, here ${\mathbf{a}}^{\mathbf{n}}{\mathbf{b}}^{\mathbf{m}}$ both are independent.

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

Grammar:

S → AB                            (This final production generates ${\mathbf{a}}^{\mathbf{+}}{\mathbf{b}}^{\mathbf{+}}$)

B → bB | b                       (This production generates ${\mathbf{b}}^{\mathbf{+}}$)

A → aA | a                       (This production generates ${\mathbf{a}}^{\mathbf{+}}$)

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 $\mathbf{L}\mathbf{ }\mathbf{=}\mathbf{ }{\mathbf{a}}^{\mathbf{n}}{\mathbf{b}}^{\mathbf{n}}{\mathbf{c}}^{\mathbf{m}}\mathbf{ }\mathbf{|}\mathbf{ }\mathbf{n}\mathbf{.}\mathbf{m}\mathbf{ }\mathbf{\ge }\mathbf{ }\mathbf{1}$.

Solution:

Here we are doing the same thing first derive grammar for ${\mathbf{a}}^{\mathbf{n}}{\mathbf{b}}^{\mathbf{n}}$ then we calculate ${\mathbf{c}}^{\mathbf{m}}$ then add them.

And from Example 9 we know the grammar of  ${\mathbf{a}}^{\mathbf{n}}{\mathbf{b}}^{\mathbf{n}}\mathbf{ }\mathbf{|}\mathbf{ }\mathbf{n}\mathbf{ }\mathbf{\ge }\mathbf{ }\mathbf{1}$ is  S → aSb | ab.

${\mathbf{c}}^{\mathbf{m}}\mathbf{ }\mathbf{|}\mathbf{ }\mathbf{m}\mathbf{ }\mathbf{\ge }\mathbf{ }\mathbf{1}$ is nothing but ${\mathbf{c}}^{\mathbf{+}}$.

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 $\mathbf{L}\mathbf{ }\mathbf{=}\mathbf{ }{\mathbf{a}}^{\mathbf{n}}{\mathbf{c}}^{\mathbf{m}}{\mathbf{b}}^{\mathbf{n}}\mathbf{ }\mathbf{|}\mathbf{ }\mathbf{n}\mathbf{.}\mathbf{m}\mathbf{ }\mathbf{\ge }\mathbf{ }\mathbf{1}$.

Solutions:

Firstly we can say it is not regular because it has infinite comparison ${\mathbf{a}}^{\mathbf{n}}{\mathbf{b}}^{\mathbf{n}}$. Now for this infinite comparison, we can design grammar easily i.e. S → aSb | ab. 

But there is ${\mathbf{c}}^{\mathbf{m}}$ in-between ${\mathbf{a}}^{\mathbf{n}}{\mathbf{b}}^{\mathbf{n}}$ .

Still, we first design simple grammar for ${\mathbf{a}}^{\mathbf{n}}{\mathbf{b}}^{\mathbf{n}}$ and ${\mathbf{c}}^{\mathbf{m}}$ 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 ${\mathbf{a}}^{\mathbf{n}}\mathbf{ }{\mathbf{c}}^{\mathbf{+}}\mathbf{ }{\mathbf{b}}^{\mathbf{n}}$)

A → Ac | c                        (This production generates ${\mathbf{c}}^{\mathbf{+}}$)

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 $\mathbf{L}\mathbf{ }\mathbf{=}\mathbf{ }{\mathbf{a}}^{\mathbf{n}}{\mathbf{b}}^{\mathbf{n}}{\mathbf{c}}^{\mathbf{m}}{\mathbf{d}}^{\mathbf{m}}\mathbf{ }\mathbf{|}\mathbf{ }\mathbf{n}\mathbf{.}\mathbf{m}\mathbf{ }\mathbf{\ge }\mathbf{ }\mathbf{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  ${\mathbf{a}}^{\mathbf{n}}{\mathbf{b}}^{\mathbf{n}}$ or ${\mathbf{c}}^{\mathbf{m}}{\mathbf{d}}^{\mathbf{m}}$ from Example 9   i.e. S → aSb | ab.

So, we can construct final grammar very easily by first generating grammar for ${\mathbf{a}}^{\mathbf{n}}{\mathbf{b}}^{\mathbf{n}}$ and then grammar for ${\mathbf{c}}^{\mathbf{m}}{\mathbf{d}}^{\mathbf{m}}$ then merge two grammars.

S → AB                                         (Final production generates ${\mathbf{a}}^{\mathbf{n}}{\mathbf{b}}^{\mathbf{n}}{\mathbf{c}}^{\mathbf{m}}{\mathbf{d}}^{\mathbf{m}}$)

B → cBd | cd                                 (This production generates ${\mathbf{c}}^{\mathbf{m}}{\mathbf{d}}^{\mathbf{m}}$)

A → aAb | ab                                (This production generates ${\mathbf{a}}^{\mathbf{n}}{\mathbf{b}}^{\mathbf{n}}$)

Example 17: 

Construct grammar for this given language $\mathbf{L}\mathbf{ }\mathbf{=}\mathbf{ }{\mathbf{a}}^{\mathbf{n}}{\mathbf{b}}^{\mathbf{2}\mathbf{n}}\mathbf{ }\mathbf{|}\mathbf{ }\mathbf{n}\mathbf{ }\mathbf{\ge }\mathbf{ }\mathbf{1}$.

Solutions:

This language is CFL because it has only infinite comparison.  It is similar to ${\mathbf{a}}^{\mathbf{n}}{\mathbf{b}}^{\mathbf{n}}$ the only difference is here b is twice of a. 

And we know the grammar of ${\mathbf{a}}^{\mathbf{n}}{\mathbf{b}}^{\mathbf{n}}\mathbf{ }\mathbf{|}\mathbf{ }\mathbf{n}\mathbf{ }\mathbf{\ge }\mathbf{ }\mathbf{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 ${\mathbf{a}}^{\mathbf{n}}{\mathbf{b}}^{\mathbf{2}\mathbf{n}}$)

Example 18: 

Construct grammar for this given language $\mathbf{L}\mathbf{ }\mathbf{=}\mathbf{ }{\mathbf{a}}^{\mathbf{n}}{\mathbf{b}}^{\mathbf{m}}{\mathbf{c}}^{\mathbf{m}}{\mathbf{d}}^{\mathbf{n}}\mathbf{ }\mathbf{|}\mathbf{ }\mathbf{n}\mathbf{.}\mathbf{m}\mathbf{ }\mathbf{\ge }\mathbf{ }\mathbf{1}$.

Solutions:

This given language is almost similar to Example 16 $\mathbf{L}\mathbf{ }\mathbf{=}\mathbf{ }{\mathbf{a}}^{\mathbf{n}}{\mathbf{b}}^{\mathbf{n}}{\mathbf{c}}^{\mathbf{m}}{\mathbf{d}}^{\mathbf{m}}\mathbf{ }\mathbf{|}\mathbf{ }\mathbf{n}\mathbf{.}\mathbf{m}\mathbf{ }\mathbf{\ge }\mathbf{ }\mathbf{1}$

This language has two infinite separate comparisons ${\mathbf{a}}^{\mathbf{n}}{\mathbf{d}}^{\mathbf{n}}$ and ${\mathbf{b}}^{\mathbf{m}}{\mathbf{c}}^{\mathbf{m}}$. 

So, first, we design grammar ${\mathbf{b}}^{\mathbf{m}}{\mathbf{c}}^{\mathbf{m}}$.

A → bAc | bc      (This production generates ${\mathbf{b}}^{\mathbf{m}}{\mathbf{c}}^{\mathbf{m}}$)

Now as we see from the given language ${\mathbf{b}}^{\mathbf{m}}{\mathbf{c}}^{\mathbf{m}}$ is in between ${\mathbf{a}}^{\mathbf{n}}{\mathbf{d}}^{\mathbf{n}}$. 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 ${\mathbf{a}}^{\mathbf{n}}{\mathbf{b}}^{\mathbf{n}}{\mathbf{c}}^{\mathbf{m}}{\mathbf{d}}^{\mathbf{m}}$)

Overall grammar

Example 19: 

Construct grammar for this given language $\mathbf{L}\mathbf{ }\mathbf{=}\mathbf{ }{\mathbf{a}}^{\mathbf{m}\mathbf{ }\mathbf{+}\mathbf{ }\mathbf{n}\mathbf{ }}{\mathbf{b}}^{\mathbf{m}\mathbf{ }}{\mathbf{c}}^{\mathbf{n}}\mathbf{ }\mathbf{|}\mathbf{ }\mathbf{n}\mathbf{.}\mathbf{m}\mathbf{ }\mathbf{\ge }\mathbf{ }\mathbf{0}$.

Solutions:

In that case, we first break the power of a and rewrite grammar as  ${\mathbf{a}}^{\mathbf{n}}\mathbf{ }{\mathbf{a}}^{\mathbf{m}}\mathbf{ }{\mathbf{b}}^{\mathbf{m}\mathbf{ }}{\mathbf{c}}^{\mathbf{n}}\mathbf{ }\mathbf{|}\mathbf{ }\mathbf{n}\mathbf{.}\mathbf{m}\mathbf{ }\mathbf{\ge }\mathbf{ }\mathbf{0}$.

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

 $\mathbf{L}\mathbf{ }\mathbf{=}\mathbf{ }{\mathbf{a}}^{\mathbf{n}}{\mathbf{b}}^{\mathbf{m}}{\mathbf{c}}^{\mathbf{m}}{\mathbf{d}}^{\mathbf{n}}\mathbf{ }\mathbf{|}\mathbf{ }\mathbf{n}\mathbf{.}\mathbf{m}\mathbf{ }\mathbf{\ge }\mathbf{ }\mathbf{1}$.

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

S → aSc | aAc                  (This production generates ${\mathbf{a}}^{\mathbf{n}}\mathbf{ }{\mathbf{a}}^{\mathbf{m}}\mathbf{ }{\mathbf{b}}^{\mathbf{m}\mathbf{ }}{\mathbf{c}}^{\mathbf{n}}$)

A → aAb | ab                   (This production generates ${\mathbf{a}}^{\mathbf{m}}\mathbf{ }{\mathbf{b}}^{\mathbf{m}}$)

Example 20: 

Construct grammar for this given language $\mathbf{L}\mathbf{ }\mathbf{=}\mathbf{ }{\mathbf{a}}^{\mathbf{n}\mathbf{ }}{\mathbf{b}}^{\mathbf{n}\mathbf{ }\mathbf{+}\mathbf{ }\mathbf{m}\mathbf{ }}{\mathbf{c}}^{\mathbf{n}}\mathbf{ }\mathbf{|}\mathbf{ }\mathbf{n}\mathbf{.}\mathbf{m}\mathbf{ }\mathbf{\ge }\mathbf{ }\mathbf{1}$

Solutions:

Same as the previous one we break the power of ‘b’ and rewrite the grammar as ${\mathbf{a}}^{\mathbf{n}}\mathbf{ }{\mathbf{b}}^{\mathbf{n}}\mathbf{ }{\mathbf{b}}^{\mathbf{m}\mathbf{ }}{\mathbf{c}}^{\mathbf{m}}$.

Now this language similar to the previous one $\mathbf{L}\mathbf{ }\mathbf{=}\mathbf{ }{\mathbf{a}}^{\mathbf{n}}{\mathbf{b}}^{\mathbf{n}}{\mathbf{c}}^{\mathbf{m}}{\mathbf{d}}^{\mathbf{m}}\mathbf{ }\mathbf{|}\mathbf{ }\mathbf{n}\mathbf{.}\mathbf{m}\mathbf{ }\mathbf{\ge }\mathbf{ }\mathbf{1}$ (Example 16)

So, we can construct grammar easily as previous was because it has two separated comparison ${\mathbf{a}}^{\mathbf{n}}{\mathbf{b}}^{\mathbf{n}}$ and ${\mathbf{b}}^{\mathbf{m}}{\mathbf{c}}^{\mathbf{m}}$.

Grammar:

S → AB                                              (This production generates ${\mathbf{a}}^{\mathbf{n}}\mathbf{ }{\mathbf{b}}^{\mathbf{n}}\mathbf{ }{\mathbf{b}}^{\mathbf{m}\mathbf{ }}{\mathbf{c}}^{\mathbf{m}}$)

B → bBc | bc                                       (This production generates ${\mathbf{b}}^{\mathbf{m}}{\mathbf{c}}^{\mathbf{m}}$)

A → aAb | ab                                      (This production generates ${\mathbf{a}}^{\mathbf{n}}{\mathbf{b}}^{\mathbf{n}}$)