FOR FREE CONTENT

Grammar Construction from Language: 

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 ‘b’ which we can say universal language by ‘a’ and ‘b’.

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 L = (a + b)  i.e  S → a | b

And from Example 3 we could understand how to design grammar for  L = (a + b)* i.e

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 L = (a + b) i.e S → a | b

 

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