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

Introduction

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) = {anbn, 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:

Q.1. Consider the grammar: 

S -> aSa|bSb|a|b

The language generated by the above grammar over the alphabet {a,b} is the set of:

(a) All palindromes

(b) All odd length palindromes.

(c) Strings that begin and end with the same symbol

(d) All even length palindromes

Correct Answer is Option (b)

Using S->a and S->b, a and b can be generated. Similarly using S=>aSa=>aba, aba can be generated. Other strings which can be generated from grammar are: a, b, aba, bab, aaa, bbb, ababa, …

Therefore, option (B) is correct.

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) = {anbn, 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:

Q.2. Which one of the following grammar generates the language L = {ai b j | i≠j}? (GATE-CS-2006)

(a)
S → AC|CB
C → aC b|a| b
A → a A|∈
B → B b|∈
(b)
S → aS|Sb| a| b
(c)
S → AC|CB
C → aC b|∈
A → a A|∈
B → B b|∈
(d)
S → A C| CB
C → aC b|∈
A → a A| a
B → Bb|b

Solution: The given language L contains the strings :

{a, b, aa, bb, aaa, bbb, aab, abb…}

It means either the string must contain one or more number of a OR one or more number of b OR a followed by b having unequal number of a and b.

If we consider grammar in option (A), it can generate ab as:

S=>AC=>aAC=>aC=>ab

However, ab can’t be generated by language L. Therefore, grammar in option (A) is not correct.
Similarly, grammar in option (B) can generate ab as:

S=>aS=>ab

However, ab can’t be generated by language L. Therefore, grammar in option (B) is not correct.

Similarly, grammar in option (C) can generate ab as:

S=>AC=>C=>aCb=>ab

However, ab can’t be generated by language L. Therefore, grammar in option (C) is not correct.

Therefore, using method of elimination, option (D) is correct.