1 of 6

Session 10: �Chomsky hierarchy of languages

By

Dr. Ashok Kumar

Amity School of Engineering & Technology

2 of 6

Chomsky hierarchy of languages

  • According to Chomsky hierarchy, grammar is divided into 4 types as follows: 
  • Type 0 is known as unrestricted grammar.
  • Type 1 is known as context-sensitive grammar.
  • Type 2 is known as a context-free grammar.
  • Type 3 Regular Grammar.

​

Amity School of Engineering & Technology

3 of 6

Chomsky hierarchy of languages

  • Type 0: Unrestricted Grammar:
  • Type-0 grammars include all formal grammar. Type 0 grammar languages are recognized by turing machine. These languages are also known as the Recursively Enumerable languages.
  • Grammar Production in the form of where

Amity School of Engineering & Technology

4 of 6

Chomsky hierarchy of languages

  • Type 1: Context-Sensitive Grammar
  • Type-1 grammars generate context-sensitive languages. The language generated by the grammar is recognized by the Linear Bound Automata 

​

Amity School of Engineering & Technology

5 of 6

Chomsky hierarchy of languages

Amity School of Engineering & Technology

6 of 6

Chomsky hierarchy of languages

Amity School of Engineering & Technology