Introduction to Noam Chomsky Grammar Classification
Avram Noam Chomsky (born December 7, 1928) is an American linguist, philosopher, and cognitive scientist who has given the hierarchy of grammar in the Theory of Computation.
Hierarchy means an organized structure in which items are arranged according to their rank or level. Chomsky has proposed such kind of hierarchy in which he has given different levels to grammar. Levels are given in terms of Type-0, Type-1, Type-2, and Type-3 on the basis of their unrestricted to restricted behavior. This behavior is based on the representation or arrangement of terminal and nonterminal in the grammar.
Noam Chomsky Grammar Type – 0 :
This type of grammar is unrestricted, or phase structured, which generates all types of languages that can be recognized by a Turing machine. These languages are called recursive enumerable languages. Unrestricted means this grammar have very less restrictions. Unrestricted grammar (G) = L → R (L is left side and R is on the right side of production) , where L, R ∈ (V ∪ T)* means any combination of terminal or non-terminal on left-hand side i,e. L as well as on right-hand side i,e. R and one left side mean “L” must have at least one variable. V stands for variable and T for terminals.
Example of Type 0 grammar: All in red are L and in blue are R
L → R
S → aSb/λ
A → aA/aB/Cb
Ba → a/Da
Noam Chomsky Grammar Type – 1 :
This is context-sensitive grammar (CSG) which is used to generate context-sensitive languages. CSG (G) = L → R, where L,R ∈ (V ∪ T)* and “L” must have at least one variable. There is one additional rule also, |L| ≤ |R|, which means the length of “L” should be less than or equal to “R”. In simple words we can say on the left of production there should be less number of terminal or non-terminal as compare to the right-hand side of production.
Example of Type – 1 grammar: All in red are L and in blue are R
L → R
S → aSb/λ
Aa → aAB/aB/Cb
B → a/Da
Noam Chomsky Grammar Type – 2 :
This is context-free grammar (CFG) which is used to generate context-free languages. CFG (G)= L → R, where R ∈ (V ∪ T)* and |L| ≤ |R|. In addition to the CSG grammar, one extra rule, that is, only a single variable is allowed in “L”.
L → R
S → aSb/λ
A → aA/aB/Cb
B → a/Da
Noam Chomsky Grammar Type – 3:
This is regular grammar, therefore language generated by these grammars is called regular languages. Regular grammar (G) = L → R, where L ≤ R , {R ∈ (T*, T*V, VT*) and u ∈ V} and “u” has only one variable.
L → R
S → aS/λ
A → aA/aB/Cb
B → a/Da
Type | Grammar | Accepted by | Production Rule | Example |
Type 0 | Unrestricted Grammar | Turing Machine (TM) | 1. x must have at least one variable (V). 2. y can be any string that consist any combination of variable (V) and terminal (T) | AB → a | Ba |
Type 1 | Unrestricted | Linear Bounded | 1. x must have at least one variable (V). 2.y can be any string that consist a combination of variable (V) and terminal (T). 3. Length of y should be less than or equal to x. | Aa → aAb | aB | Cb |
Type 2 | Context Free | Push Down | 1. x can have exactly one Variable (V). 2. y can be any string that consists a combination of variable (V) and terminal (T). 3. Length of y should be less than or equal to x. | A → aBa | aB | Ba |
Type 3 | Regular | Finite Automata (FA) | 1. x can have exactly one Variable (V) 2. y can be any string that consists of any combination from (VT*, T*V, T*), where V = one variable and T* = any number of terminals. 3. Length of y should be less than or equal to x. | A → a | Bb | bB |
