Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

312 LANGUAGES, AUTOMATA, GRAMMARS [CHAP. 12

Types of Grammars

Grammars are classified according to the kinds of production which are allowed. The following grammar
classification is due to Noam Chomsky.
A Type 0 grammar has no restrictions on its productions. Types 1, 2, and 3 are defined as follows:
(1) A grammarGis said to be of Type 1 if every production is of the formα→βwhere|α|≤|β|or of the
formα→l.

(2) A grammarGis said to be of Type 2 if every production is of the formA→βwhere the left sideAis a

nonterminal.

(3) A grammarGis said to be of Type 3 if every production is of the formA→aorA→aB, that is, where
the left sideAis a single nonterminal and the right side is a single terminal or a terminal followed by a
nonterminal, or of the formS→l.
Observe that the grammars form a hierarchy; that is, every Type 3 grammar is a Type 2 grammar, every Type
2 grammar is a Type 1 grammar, and every Type 1 grammar is a Type 0 grammar.
Grammars are also classified in terms of context-sensitive, context-free, and regular as follows.

(a) A grammarGis said to becontext-sensitiveif the productions are of the form

αAα′→αβ α′

The name “context-sensitive” comes from the fact that we can replace the variableAbyβin a word only

whenAlies betweenαandα′.

(b) A grammarGis said to becontext-freeif the productions are of the form

A→β

The name “context-free” comes from the fact that we can now replace the variableAbyβregardless of

whereAappears.

(c) A grammarGis said to beregularif the productions are of the form

A→a, A→aB, S→l

Observe that a context-free grammar is the same as a Type 2 grammar, and a regular grammar is the same as a
Type 3 grammar.
A fundamental relationship between regular grammars and finite automata follows.

Theorem 12.4: A languageLcan be generated by a Type 3 (regular) grammarG, if and only if there exists a
finite automatonMwhich acceptsL.
Thus a languageLis regular iffL=L(r)whereris a regular expression iffL=L(M)whereMis a finite
automaton iffL=L(G)whereGis a regular grammar. (Recall that “iff” is an abbreviation for “if and only if.”)

EXAMPLE 12.12 Consider the languageL={anbn|n> 0 }.

(a) Find a context-free grammarGwhich generatesL.

Clearly the grammarGwith the following productions will generateL:

S→ab, S→aSb

Note thatGis context-free

(b) Find a regular grammarGwhich generatesL.

By Example 12.8,Lis not a regular language. ThusLcannot be generated by a regular grammar.