Computer Science Engineering (CSE) Exam  >  Computer Science Engineering (CSE) Notes  >  Theory of Computation  >  Relationship Between Grammar & Language

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

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

Question for Relationship Between Grammar & Language
Try yourself:Consider the grammar: (GATE-CS-2009)
S -> aSa|bSb|a|b 
The language generated by the above grammar over the alphabet {a,b} is the set of:
View Solution

Question for Relationship Between Grammar & Language
Try yourself:Consider the following context-free grammars: (GATE-CS-2016)
G1: S→aS/B, B→b/bB
G2: S→aA|bB, A→aA|B|ε, B→bB|ε
Which one of the following pairs of languages is generated by G1 and G2, respectively?
View Solution

➤ 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:

Question for Relationship Between Grammar & Language
Try yourself:Which one of the following grammar generates the language L = {ai bj | i≠j}? (GATE-CS-2006)
View Solution

The document Relationship Between Grammar & Language | Theory of Computation - Computer Science Engineering (CSE) is a part of the Computer Science Engineering (CSE) Course Theory of Computation.
All you need of Computer Science Engineering (CSE) at this link: Computer Science Engineering (CSE)
18 videos|69 docs|44 tests

Top Courses for Computer Science Engineering (CSE)

18 videos|69 docs|44 tests
Download as PDF
Explore Courses for Computer Science Engineering (CSE) exam

Top Courses for Computer Science Engineering (CSE)

Signup for Free!
Signup to see your scores go up within 7 days! Learn & Practice with 1000+ FREE Notes, Videos & Tests.
10M+ students study on EduRev
Related Searches

Important questions

,

Previous Year Questions with Solutions

,

Objective type Questions

,

study material

,

video lectures

,

Semester Notes

,

mock tests for examination

,

ppt

,

Sample Paper

,

practice quizzes

,

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

,

shortcuts and tricks

,

Viva Questions

,

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

,

Exam

,

MCQs

,

pdf

,

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

,

Summary

,

Extra Questions

,

Free

,

past year papers

;