chomsky hierachy

 Chomsky Hierachy(1959)

The great scientist Chomsky, it gives a hierarchy of grammar audible into the type that is type 3 grammar, type 2 grammar type 1, grammar, and Type 0 grammar. type 3 grammar is the most restricted grammar while Type 0 is unrestricted grammar.

TYPE -0 

Type 0 grammar is also called face structure grammar or unrestricted grammar. The language used in this type of grammar is type 0 language. Turing machine is based on Type 0 language. it is represented as Alpha(α) tends to beta(β).

                                                    α   →  β

where alpha contains any combination of terminals and nonterminals, there should be at least one nonterminal at LHS or alpha side, whereas beta can be terminal or nonterminal.

TYPE - 1

Type 1 grammar is also called context-sensitive grammar. The language used in this type of grammar is type 1 language. linear bounded automata are based on type -1. 

for example:

                            α   →  β

                              | α |≤|β|     and there should be no null set on the right-hand side.

All Type 1 Grammars are Type 0 but vice versa are not true.

TYPE - 2

type 2 grammar is also called context-free grammar. the language used is contest-free language.

push down automata or PDAs are based on this type of grammar.

for example:

                             α   →  β

                                  | α|=1

TYPE -3

Type 3 grammar is also called regular grammar and the language used in this is type 3 language.

finite automata are based on Type 3 grammar.

for example: 

                          α   →  β

                                  | α|=1, where β Is a single Terminal followed by a single nonterminal.