O'Reilly logo

Introduction to Formal Languages, Automata Theory and Computation by Kamala Krithivasan, R Rama

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Chapter 2. Grammars

The idea of a grammar for a language has been known in India since the time of Panini (about 5th century B.C). Panini gave a grammar for the Sanskrit language. His work on Sanskrit had about 4000 rules (Sutras). From that, it is clear that the concept of recursion was known to the Indians and was used by them in very early times.

In 1959, Noam Chomsky tried to give a mathematical definition for grammar. The motivation was to give a formal definition for grammar for English sentences. He defined four types of grammar viz., type 0, type 1, type 2, and type 3. At the same time, the programming language ALGOL was being considered. It was considered as a block-structured language and a grammar was required which could describe all ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required