Mathematical Foundation of Computer Science

DHARM

NON-REGULAR GRAMMARS 279

Regular

Language

Co

nt

ext

SensitiveLang

ua

ge

C

on

tex

tFreeLangu

ag

e

Re

cu

rsi

veE

numerableLa

ngu

ag

e

Type-0 Language

Type-1 Language

Type-2 Language

Type-3 Language

Fig. 11.0
So the classification of grammars canbe heirarchly arranged, which is shown in Fig. 11.0.
This arrangement is known as Chomesky’s heirarchy. Alternatively we say that
l A type-3 language has the property of , type-2 language, type-1 language & type-0
language.
l A type-2 language has the property of type-1 language & type-0 language.
l A type-1 language has the property of type-0 language.

Example 10.1. A grammar (G) is defined as, G = (VT, VN, S, P) where VT = {a, b}; VN = {S, A, B}
and the set of productions P = {S → aB, S → bA, A → a, A → aS, A → bAA, B → b, B → bS, B →
aBB} then at any stage of productions propagation if,
aa B BAb ⇒ aa aBB BAb
α 1 α 2 α 1 α 2
then, B → aBB is a production (∈ P)
(example of Type-2 grammar)
The language of the grammar G is given by L(G) where L(G) contains following set of
string/s:
S ⇒ aB
⇒ aaB B [∴ B → aBB] now we expand against
rightmost nonterminal symbol (B) first
⇒ aa B aBB [∴ B → aBB]
⇒ aabSa B B [∴ B → bS]
⇒ aab S abB[∴ B → b]
⇒ aabbAab B[∴ S → bA]
⇒ aabbAabb [∴ B → b]
⇒ aabbaabb [∴ A → a]

or S ⇒N aabbaabb

Hence, aabbaabb ∈ L(G). Similarly many strings can be generated using the produc-
tions that are the in language of G.

⇒N The relation (deriving in zero or finite number of steps) is reflexive and transitive

i.e. If X ⇒N X then it concluded that X ⇒ X in zero step, hence reflexive, and if X ⇒N Y and Y ⇒

Z in one step then certainly X ⇒N Y on some finite step/s.