Chomsky Hierarchy in Theory of Computation(TOC)

Introduction

The Chomsky Hierarchy represents the class of languages that are accepted by the different machines. It provides a framework for understanding the limitations and capabilities of different grammar and formal languages. 

In this article, we will explore the Chomsky Hierarchy in detail and its significance in the theory of computation (TOC).

What is Chomsky hierarchy in TOC?

The Chomsky hierarchy is a system for classifying formal grammars and languages in computer science and linguistics. It consists of four levels, which describe increasingly complex types of languages that can be generated by formal grammars. These levels are Type 0 (unrestricted), Type 1 (context-sensitive), Type 2 (context-free), and Type 3 (regular). The hierarchy is named after Noam Chomsky, who proposed it as a way of characterizing the expressive power of different types of formal languages and grammars. It is a fundamental concept in the study of formal languages and is used in the development of parsing algorithms and other tools for working with formal languages.

According to the given hierarchy, Grammar is divided into four types

Type 0: Unrestricted Grammar

Language recognized by Turing Machine is known as Type 0 Grammar. They are also known as Recursively Enumerable Languages.

Grammar Production for Type 0 is given by

α —> β

For Example:

Sba —> a
S —> B

Where S and B are Variables And a and b are Terminals.

Type 1: Context-Sensitive Grammar

Languages recognized by Linear Bound Automata are known as Type 1 Grammar. Context-sensitive grammar represents context-sensitive languages.

For grammar to be context-sensitive, it must be unrestricted. Grammar Production for Type 1 is given by

α —> β (ensuring count symbol in LHS must be less than or equal to RHS)

For Example,

S —> BA
BA —> bca
B —> b

Type 2: Context-Free Grammar

Languages recognized by Pushdown Automata are known as Type 2 Grammar. Context-free grammar represents context-free languages.

For grammar to be context-free, it must be context-sensitive. Grammar Production for Type 2 is given by

A —> α

Where A is a single non-terminal.

For Example,

A —> aB
B —> b

Type 3: Regular Grammar

Languages recognized by Finite Automata are known as Type 3 Grammar. Regular grammar represents regular languages.

For grammar to be regular, it must be context-free. Grammar Production for Type 3 is given by

V → T*V / T*  

For Example,

A —> ab

Also read,  Arden's theorem