Chomsky Hierarchy is a broad classification of the various types of grammar available

These include Unrestricted grammar, context-free grammar, context-sensitive grammar and restricted grammar

Grammars are classified by the form of their productions.

Each category represents a class of languages that can be recognized by a different automaton

The classes are nested, with type 0 being the largest and most general, and type 3 being the smallest and most restricted.

Type 0 :Unrestricted grammar : This type of grammar requires LHS to contain atleast one non-terminal

Applications: Unrestricted language recursively enumerable automaton Turing machine.

– x → y – x ∈ ((V ∪ T)∗V (V ∪ T)∗) – y ∈ (V ∪ T)∗

– LHS contains at least one non-terminal

– generate recursively enumerable languages

– recognized by Turing Machines

– example :

generates L = {ww | w ∈ (a + b)*}

Generate wCwR E

C is a temporary center marker

E is a wall

∗ Reverse $w^R$ by pushing symbols in $w^R$, leftmost first, over the wall with a pusher P

∗ Clean up by removing C and E

V = {S, T, C, P}

T = {a, b} P :

1. S → TE

2. T → aTa

3. T→ | bTb

4. T→ | C

5. C → CP

6. Paa → aPa

7. Pab → bPa

8. Pba → aPb

9. Pbb → bPb

10. PaE → Ea

11. PbE → Eb

12. CE → є

Type 1 : Context-sensitive grammar

Applications: context-sensitive language context-sensitive automaton linear-bounded automaton – x → y

or S → є and S is not in RHS.

– x∈ ((V ∪ T)∗V (V ∪ T)∗)

– y∈ (V ∪ T)+ – |x| ≤ |y| – non-contracting

– generate context-sensitive languages

– recognized by linear-bounded automata

– example

V = {S, A, B}

T = {a, b, c}

P :

1. S → abc

2. | aAbc

3. Ab → bA

4. Ac → Bbcc

5. bB → Bb

6. aB → aa

7. aB → aaA

generates L =${a^nb^nc^n| n ≥ 1}$

Type 2 : Context-free -It is a grammar that is used to generate languages recursively and requires it to be in Chomsky Normal Form or the Griebach Normal Form

Applications: context-free language context-free automaton pushdown automaton

– x → y

– x∈ V

– y∈ (V ∪ T)*

– generate context-free languages

– recognized by pushdown automata

– example

V = {S}

T = {a, b}

P :

1. S → aSb

2.S → |є

generates L = {a^nb^n| n ≥ 0}

Type 3 : Regular grammar

– A regular grammar is right-linear or left- linear (but not both)

– A, B ∈ V

– y∈ T*

– Right-Linear productions have the form A → yB or A → y

– Left-Linear productions have the form A → By or A → y

– generate regular languages

– recognized by finite state automata

– example

V = {S}

T = {a}

P :

1. S → aS

2. . S → |є

generates L = ${a^n; | n ≥ 0}$