SOLUTION: • 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 at least 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 wCwREwCwRE

C is a temporary center marker

E is a wall

∗ Reverse wRwR by pushing symbols in wRwR, 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→TE1.S→TE

2.T→aTa2.T→aTa

3.T→|bTb3.T→|bTb

4.T→|C4.T→|C

5.C→CP5.C→CP

6.Paa→aPa6.Paa→aPa

7.Pab→bPa7.Pab→bPa

8.Pba→aPb8.Pba→aPb

9.Pbb→bPb9.Pbb→bPb

10.PaE→Ea10.PaE→Ea

11.PbE→Eb11.PbE→Eb

12.CE→є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→abc1.S→abc

2.|aAbc2.|aAbc

3.Ab→bA3.Ab→bA

4.Ac→Bbcc4.Ac→Bbcc

5.bB→Bb5.bB→Bb

6.aB→aa6.aB→aa

7.aB→aaA7.aB→aaA

generates L=anbncn|n≥1L=anbncn|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→aSb1.S→aSb

2.S→|є2.S→|є

generates L=anbn|n≥0L=anbn|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→aS1.S→aS

2..S→|є2..S→|є

generates L=an;|n≥0L=an;|n≥0$