4
Formal Languages
In this chapter \ve introduce the concepts of grammars and formal languages
and discuss the Chomsky classification of languages. We also study the
inclusion relation between the four classes of languages. Finally. we discuss the
closure properties of these classes under the variuus operations.
4.1 BASIC DEFINITIONS AND EXAMPLES
The theory of formal languages is an area with a number of applications in
computer science. Linguists were trying in the early 1950s to define precisely
valid sentences and give structural descriptions of sentences. They wanted to
define a fomlal grammar (i.e. to describe the rules of grammar in a rigorous
mathematical way) to describe English. They tbought that such a desCliption of
natural languages (the languages that we use in everyday life such as English,
Hindi. French, etc.) would make language translation using computers easy. It
was Noam Chomsky who gave a mathematical model of a grammar in 1956.
Although it was not useful for describing natural languages such as English, it
turned alit to be useful for computer languages. In fact. the Backus-Naur form
used to describe ALGOL followed the definition of grammar (a context-free
grammar) given by Chomsky.
Before giving the definition of grammar, we shall study, for the sake of
simplicity. two types of sentences in English with a view to formalising the
construction of these sentences. The sentences we consider are those \vith a
nOL"; and a verb, or those with a noun-verb and adverb (such as 'Ram ate
quickly' or 'Sam ran '). The sentence 'Ram ate quickly' has the words 'Ram',
'ate', 'quickly' written in that order, If we replace 'Ram' by 'Sam', 'Tom',
'Gita', etc. i.e. by any noun, 'ate' by 'ran', 'walked', etc. i.e, by any verb in the
107
Formal Languages
In this chapter \ve introduce the concepts of grammars and formal languages
and discuss the Chomsky classification of languages. We also study the
inclusion relation between the four classes of languages. Finally. we discuss the
closure properties of these classes under the variuus operations.
4.1 BASIC DEFINITIONS AND EXAMPLES
The theory of formal languages is an area with a number of applications in
computer science. Linguists were trying in the early 1950s to define precisely
valid sentences and give structural descriptions of sentences. They wanted to
define a fomlal grammar (i.e. to describe the rules of grammar in a rigorous
mathematical way) to describe English. They tbought that such a desCliption of
natural languages (the languages that we use in everyday life such as English,
Hindi. French, etc.) would make language translation using computers easy. It
was Noam Chomsky who gave a mathematical model of a grammar in 1956.
Although it was not useful for describing natural languages such as English, it
turned alit to be useful for computer languages. In fact. the Backus-Naur form
used to describe ALGOL followed the definition of grammar (a context-free
grammar) given by Chomsky.
Before giving the definition of grammar, we shall study, for the sake of
simplicity. two types of sentences in English with a view to formalising the
construction of these sentences. The sentences we consider are those \vith a
nOL"; and a verb, or those with a noun-verb and adverb (such as 'Ram ate
quickly' or 'Sam ran '). The sentence 'Ram ate quickly' has the words 'Ram',
'ate', 'quickly' written in that order, If we replace 'Ram' by 'Sam', 'Tom',
'Gita', etc. i.e. by any noun, 'ate' by 'ran', 'walked', etc. i.e, by any verb in the
107