Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Last Updated: Apr 13, 2024
Difficulty: Easy

Chomsky Hierarchy in Theory of Computation(TOC)

Leveraging ChatGPT - GenAI as a Microsoft Data Expert
Speaker
Prerita Agarwal
Data Specialist @
23 Jul, 2024 @ 01:30 PM

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).

Chomsky Hierarchy in 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 0Unrestricted Grammar
Type 1Context-Sensitive Grammar
Type 2Context-Free Grammar
Type 3Regular Grammar
Types of Chomsky Hierarchy

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 GrammarContext-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

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Frequently Asked Questions

What is Chomsky hierarchy in TOC?

The Chomsky hierarchy is a classification of formal grammar in computer science and linguistics. It consists of four levels, which describe increasingly complex types of languages that can be generated by formal grammar.

What is Chomsky hierarchy used for?

The Chomsky hierarchy is used to classify formal languages according to their complexity and expressiveness and to help in the development of parsing algorithms and other tools for working with formal languages in computer science and linguistics.

What are the levels of Chomsky grammar?

The Chomsky hierarchy consists of four levels, which are Type 0 (unrestricted), Type 1 (context-sensitive), Type 2 (context-free), and Type 3 (regular). The levels are based on the complexity of the formal grammar needed to generate a language.

What are the 4 classifications of grammars by Chomsky?

There are mainly 4 classifications of grammars by Chomsky. These four classifications are Type 0: Unrestricted Grammar, Type 1: Context-Sensitive Grammar, Type 2: Context-Free Grammar, and Type 3: Regular Grammar. 

What are the three theories of grammar?

The three main theories of grammar include Prescriptive Grammar, Descriptive Grammar, and Generative Grammar. Prescriptive grammar focuses on how the language should be used, descriptive grammar focuses on how the language should be used in real practice.

Conclusion

This article covered concepts of Chomsky's Hierarchy and its types. 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. 

Recommended Readings:


Check out some of the amazing Guided Paths on topics such as Data Structure and AlgorithmsCompetitive ProgrammingBasics of C, Basics of Javaetc. along with some Contests and Interview Experiences only on Coding Ninjas Studio

Topics covered
1.
Introduction
2.
What is Chomsky hierarchy in TOC?
2.1.
Type 0: Unrestricted Grammar
2.2.
Type 1: Context-Sensitive Grammar
2.3.
Type 2: Context-Free Grammar
2.4.
Type 3: Regular Grammar
3.
Frequently Asked Questions
3.1.
What is Chomsky hierarchy in TOC?
3.2.
What is Chomsky hierarchy used for?
3.3.
What are the levels of Chomsky grammar?
3.4.
What are the 4 classifications of grammars by Chomsky?
3.5.
What are the three theories of grammar?
4.
Conclusion