0
Write Short Notes on Chomsky Hierarchy

Mumbai university > Comp > SEM 4 > TCS

Marks: 10M

Year: May 2014,Dec 2014

0  upvotes
0
  • 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.

enter image description here

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}$$

0  upvotes
Please log in to add an answer.

Next up

Read More Questions

If you are looking for answer to specific questions, you can search them here. We'll find the best answer for you.

Search

Study Full Subject

If you are looking for good study material, you can checkout our subjects. Hundreds of important topics are covered in them.

Know More