CREATE OWN LIBRARY

Subject Mock

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 $L = a^{n} | n \geq 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 $L = a^{n} b^{n} | n \geq 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 $a^{n} b^{n} | n \geq 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

Please Login to Bookmark

Contributed by

Debashis Roy Faculty of Computer Science Department, JCC College, University of Calcutta