# CREATE OWN LIBRARY

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

Solution:

This language is not same as  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 .

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   is  S → aSb | ab.

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 .

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 )

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

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 .

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  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 .

Solutions:

This given language is almost similar to Example 16

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 .

Solutions:

In that case, we first break the power of a and rewrite grammar as  .

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

.

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

S → aSc | aAc                  (This production generates )

A → aAb | ab                   (This production generates )

Example 20:

Construct grammar for this given language

Solutions:

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

Now this language similar to the previous one  (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 )

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}}$)