Chomsky Classification of Languages

In the definition of a grammar (V.v, 2:, P, S), VV and 2: are the sets of symbols and SEVy. So if we want to classify grammar. we have to do it only by considering the form of production. Chomsky classified grammar into four types in terms of productions (types 0-3).

A type 0 grammar is any phrase structure grammar without any restrictions. (All the grammars we have considered are type 0 grammars.) To define the other types of grammar. we need a definition. In a production of the fom1 cp Alfl ~ rpCXljf, where A is a variable, rp is called the left context, ljf the right context and rpcxlfl the replacement string.