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^{n}b^{n}, n>=0}
In language L(G) discussed above, the condition n = 0 is taken to accept ε.
➤ Key Points –
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^{n}b^{n}, 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 –
Let us discuss questions based on this:
18 videos56 docs44 tests

18 videos56 docs44 tests


Explore Courses for Computer Science Engineering (CSE) exam
