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