Relationship Between Grammar & Language | Theory of Computation - Computer Science Engineering (CSE) PDF Download

Clear all your Computer Science Engineering (CSE) doubts with EduRev Join for Free

Join for Free

Relationship between grammar and language in Theory of Computation

A grammar is a set of production rules which are used to generate strings of a language. In this article, we have discussed how to find the language generated by a grammar and vice versa as well.

➤ Language generated by a grammar –
Given a grammar G, its corresponding language L(G) represents the set of all strings generated from G. Consider the following grammar,
G: S-> aSb|ε
In this grammar, using S-> ε, we can generate ε. Therefore, ε is part of L(G). Similarly, using S=>aSb=>ab, ab is generated. Similarly, aabb can also be generated.
Therefore,
L(G) = {aⁿbⁿ, n>=0}
In language L(G) discussed above, the condition n = 0 is taken to accept ε.

➤ Key Points –

• For a given grammar G, its corresponding language L(G) is unique.
• The language L(G) corresponding to grammar G must contain all strings which can be generated from G.
• The language L(G) corresponding to grammar G must not contain any string which can not be generated from G.

Let us discuss questions based on this:

➤ Grammar generating a given language –

Given a language L(G), its corresponding grammar G represents the production rules which produces L(G). Consider the language L(G):
L(G) = {aⁿbⁿ, n>=0}
The language L(G) is set of strings ε, ab, aabb, aaabbb….

For ε string in L(G), the production rule can be S->ε.

For other strings in L(G), the production rule can be S->aSb|ε.

Therefore, grammar G corresponding to L(G) is:
S->aSb| ε
Key Points –

• For a given language L(G), there can be more than one grammar which can produce L(G).
• The grammar G corresponding to language L(G) must generate all possible strings of L(G).
• The grammar G corresponding to language L(G) must not generate any string which is not part of L(G).

Let us discuss questions based on this: