Chomsky Hierarchy with Examples | TOC

Chomsky hierarchy is a hierarchical arrangement of classes of formal grammar. According to Chomsky's Hierarchy, grammar is of four types, which are as follows: Type 0 grammar is unrestricted grammar and is recognized using a Turing machine. Type 1 grammar is context-sensitive grammar and is recognized using a Linear Bounded Automata. Type 2 grammar is context-free grammar and is recognized using a Push Down Automata. Type 3 grammar is regular grammar and is recognized using a Finite Automata.

Type 0: Unrestricted Grammar: Type-0 grammars include all formal grammar and are known as unrestricted grammar. Type 0 grammar languages are recognized by turing machine. The language accepted by this type of grammar are also known as the Recursively Enumerable languages. Type 0 grammar has a Production in the form of [α→β] where α is ( V + T)* V ( V + T)* V : Variables T : Terminals. β is ( V + T )*. Note: In type 0 there must be at least one variable on the Left side of production.

Type 1: Context-sensitive Grammar: Type-1 grammars are context-sensitive grammars and generate context-sensitive language. Type 1 grammar languages are recognized by linear bounded automata. The language accepted by this type of grammar is context-sensitive language.

Type 1 grammar has a Production in the form of [α→β] where α is ( V + T)* V ( V + T)* V : Variables T : Terminals. β is ( V + T )+. Note: In type 0 there must be at least one variable on the Left side of production.

Type 2: Context-free Grammar: Type-2 grammars are context-free grammars and generate context-free language. Type 2 grammar languages are recognized by push-down automata. The language accepted by this type of grammar is context-free language. The left-hand side of production can have only one variable and there is no restriction on the right-hand side of production. That is,

[α]=1

Type 3: Regular Grammar: Type-3 grammars generate regular languages. Regular languages are accepted by a finite-state automaton. Type 3 is the most restricted form of grammar. The grammar should be in the given form only V →VT/T (left-regular grammar) V→TV/T (right-regular grammar) Where V is variable and T is terminal.

All the grammars are related to each other in such a way that, Regular grammar ⊃ Context-free Grammar ⊃ Context-sensitive grammar ⊃ Unrestricted Grammar.

Chomsky Hierarchy in TOC: https://www.geeksforgeeks.org/chomsky-hierarchy-in-theory-of-computation/