We already see the definition of grammar in the previous __chapter__**.**

We also see construct language from grammar from the __chapter (Identify Language from grammar)__**.**

Before starting to construct grammar from a certain language we have to know some important and language and corresponding grammar from the __chapter (Important few grammars must remember)__**.**

__Generates grammar from Language__

__Example 1:__

Consider a finite language **L = {aa, ab, ba, bb}****, **∑** = {a,b}**. Write the corresponding grammar.

__Solution:__

For any finite language, it is very easy to construct a grammar from language i.e. number combination of strings of the language is basically direct production of the grammar.

Like,

G = ({S}, {a, b}, {S}, {P})

P: **S → aa / ab / ba / bb**.

__Another similar example__

Finite Language **L= (a + b) (a + b)**

Here (a + b) means either a or b.

So, how many strings we can get from this language L = {aa, ab, ba, bb}

__Corresponding grammar __

G = ({S}, {a, b}, {S}, {P})

P: S → AA ** (**From this production we will get **(a + b) (a + b))**

A → a | b **(**From this production we will get **(a + b))**

__Example 2:__

Consider a language $\mathbf{L}\mathbf{}\mathbf{=}\mathbf{}{\mathbf{a}}^{\mathbf{n}}\mathbf{}\mathbf{|}\mathbf{}\mathbf{n}\mathbf{}\mathbf{\ge}\mathbf{}\mathbf{0}$**. **Construct the corresponding grammar.

__Solution:__

This language is an infinite language and strings which contain by this language are {λ , a, aa, aaa, aaaa……).

Now for the smallest string **λ**, we can write the grammar **S → ∊**.

And for single **‘a’** we can write the grammar **S → a**.

Now we can repeat **‘a’** for any number of times in that case for the repeated string we write

**S → aS | ∈**** **(This production generates an infinite number of **‘a’**** **which is **a***** (Closer of a).**

Any combination of this does not affect the language like:

**S → aS | ∈**** = ****S → Sa | ∈**** **

**Note:**** **In place of **S** whatever we put in this position we will get closer of this string - (string)*

**A → aA | ∈** and **A → Aa | ∈** are the same. Because a given language has many representations of grammar.

__Example 3:__

Consider a language **L = (a + b)*****. **Construct the corresponding grammar.

__Solution:__

This language is a set of all possible strings generated by * ‘a’* and

Now we know **(a+b)* = (a*b*)*** **(**__For details see Chapter All form of (a+b)*__**)**

We know the grammar of **a* and b*** is **S → aS | ∈ and S → bS | ∈ **correspondingly.

Now we have designed grammar for all combinations of **a* and b*** i.e. **(a*b*)*****.**

So, we can write to gather **S → aS | bS | ∈**** (This grammar generates ****L = (a + b)*****)**

__Example 4:__

Language **L = Set of all string generated by ****a**** and ****b**** with at ****least 2 length**, ∑** = {****a****, ****b****}**

i.e. Regular Expression: **(a + b) (a + b) (a + b)***. Construct the grammar.

__Solution:__

Given Language is **L = (a + b) (a + b) (a + b)*****. **But one thing should keep in our mind that we can’t write regular expressions for all. We can write regular expressions only for **regular**.

From ** Example 1** we understand how to design grammar for

And from

**S → aS | bS | ∈**

So, we can easily construct grammar for language **L = (a + b) (a + b) (a + b)***

**S → AAB (**This production generates **(a + b) (a + b) (a + b)*)**

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

**B → aB | bB | ϵ** **(**This production generates** (a + b)*)**

__Example 5:__

Language **L = Set of all string generated by ****a**** and ****b**** with at ****most 2 lengths**, ∑** = {****a****, ****b****}.** Construct the grammar.

__Solution:__

As per the given language, we can write the regular expression for it because it is finite and regular language.

Regular expression of given language: RE = **(a + b + λ) ( a + b + λ)**

**(a + b + λ)**** means it should ****a or b or λ****. **

From ** Example 1** we understand how to design grammar for

So, we can easily design grammar for **L = (a + b + λ) **which is **S → a | b | λ**

So, grammar for given language L = **(a + b + λ) (a + b + λ)****.**

**S → AA (**This production generates **(a + b + λ) (a + b + λ))**

**A → a | b | ϵ (**This production generates **(a + b + λ))**

__Example 6:__

Consider a language L = Set of all strings **starting with a and ending with b**, ∑** = {****a****, ****b****}.** Construct the corresponding grammar.

__Solution:__

This is regular grammar and we can write regular expressions for it.

Regular expression: **RE = a(a+b)* b**

So, we can construct the grammar for it.

**S → aBb (**This production generates **a(a + b)*b)**

**A → aA | bA | ϵ (**This production generates **(a + b)*)**

__Example 7:__

Consider a language L = Set of all strings **starting and ending with different symbol, **∑** = {****a****, ****b****}.** Construct the corresponding grammar.

__Solution:__

This is regular grammar and we can write regular expressions for it.

Regular expression: **RE = a(a + b)* b + b(a +b )* a**

So, we can construct the grammar for it.

**S → aAb | bAa (**This production generates **a(a + b)*b + b(a + b)*a))**

**A → aA | bA | ϵ (**This production generates **(a + b)*)**

__Example 8:__

Consider a language L = Set of all strings **starting and ending with the same symbol, **∑** = {****a****, ****b****}**. Construct the corresponding grammar.

__Solution:__

This is regular grammar and we can write regular expressions for it.

Regular expression: **RE = a(a + b)* a + b(a + b)* b**

The construction of this grammar is similar to the previous one (** Example 7**) the only difference is this language contains empty string also.

**S → aAa | bAb | a | b | ϵ (**This production generates **a(a + b)*a + b(a + b)*b))**

**A → aA | bA | ϵ (**This production generates **(a + b)*)**

__Example 9:__

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

__Solution:__

In that case, we can’t write regular expression for it because it is not regular even it is a **Context Free Language (CFL)**** (For Details see **__How to identify language__** ****)**

We can already see the grammar in the previous chapter __Important few grammars must remember__**.**

__Grammar of corresponding given language__

**S → aSb | ab (**This production generates ${\mathbf{a}}^{\mathbf{n}}{\mathbf{b}}^{\mathbf{n}}\mathbf{}\mathbf{|}\mathbf{}\mathbf{n}\mathbf{}\mathbf{\ge}\mathbf{}\mathbf{1}$**)**

We use this production **S → aSb** for generates repeated times ‘a followed by b,

And put **S → ab** to stop the string and this language not contain any empty string because **n ≥ 1****.**

__Example 10:__

Given language L = **Set of all palindromes. **Construct the corresponding grammar.

__Solution:__

Set of all palindromes = set of even palindrome **+ **set of add palindrome.

__Grammar for the set of all palindromes:__

**Please follow the rest of** __examples 11 - 20 in the next chapter __

Contributed by