- Trending Categories
- Data Structure
- Networking
- RDBMS
- Operating System
- Java
- iOS
- HTML
- CSS
- Android
- Python
- C Programming
- C++
- C#
- MongoDB
- MySQL
- Javascript
- PHP

- Selected Reading
- UPSC IAS Exams Notes
- Developer's Best Practices
- Questions and Answers
- Effective Resume Writing
- HR Interview Questions
- Computer Glossary
- Who is Who

In order to understand the relationship between the grammar and language in the theory of computation (TOC), let us understand what is language generated by grammar in TOC.

The grammar is S-> aSb| E.

In this grammar, by using S-> E, we can generate E.

Therefore, E is part of L(G).

Similarly, by using S=>aSb=>ab, ab is generated.

Similarly, aabb can also be generated.

Therefore, the result is as follows −

L(G) = {a^{n}b^{n}, n>0}

In language L(G) which is discussed above, the condition n =0 is taken to accept the epsilon.

Consider the grammar given below

S -> aSa | bSb | a |b

Now, let us find out what language is generated by the above grammar over the alphabet {a,b}.

Using S->a and S->b,

a and b can be generated.

Similarly by using S->aSa

->aba

aba can be generated.

Other strings which can be generated from grammar are as follows −

a,b,aba,bab,aaa,bbb,ababa,.....

Therefore, the language generated for the given grammar over the alphabet {a,b} is the set of all odd length palindromes.

- Related Questions & Answers
- Explain the concept of grammar in TOC
- Explain Operator grammar and precedence parser in TOC
- Explain Type-0 grammar in TOC
- Explain Type-1 grammar in TOC
- Explain Type-2 and Type-3 Grammar in TOC?
- Explain the simplification of context free grammar in TOC
- Explain about left linear regular grammar in TOC
- Explain the relationship between Finite Automata and Regular Expression.
- Explain the different operations on Regular language in TOC.
- What is unambiguous grammar in TOC?
- Explain formal definition of language with examples in TOC?
- What do you mean by grammar and production in TOC?
- Explain Set relations and operations in TOC?
- Differentiate between Ambiguous and Unambiguous Grammar
- What is the relationship between correlation and covariance?

Advertisements