• 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 $wCw^R 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}$$