Introduction
- The concept of Chomsky Classification was developed by linguist Noam Chomsky in 1956.
- The Chomsky Classification is also known as the Chomsky hierarchy.
Definition
- The Chomsky Classification is a hierarchy that categorizes grammars and languages into four types based on their generative power and computational models.
- The Chomsky hierarchy is a classification of formal grammars and the languages they generate, and ranks grammars by their generative power and describes the corresponding automata that recognize them.
Characteristics
- Each higher type of Chomsky Classification includes all lower types.
Types of Chomsky Classification
The Chomsky Classification (Chomsky Hierarchy) divides formal grammars into four types-
- Type 3
- Type 2
- Type 1
- Type 0
| Type | Grammar Type | Language Class | Recognizer/Automaton/Recognizing Machine | Production Rules | Example Language |
| Type 0 | Unrestricted Grammar | Recursively Enumerable Languages | Turing Machine | α → β (no restrictions) where contains at least one variable | Any computable language |
| Type 1 | Context-Sensitive Grammar | Context-Sensitive Languages | Linear-Bounded Automaton | αAβ → αγβ length of RHS ≥ LHS | aⁿbⁿcⁿ |
| Type 2 | Context-Free Grammar | Context-Free Languages | Pushdown Automaton | A → γ where is a single non-terminal | aⁿbⁿ |
| Type 3 | Regular Grammar | Regular Languages | Finite State Automaton | A → aB or A → a | a* |
Type 3 : Regular Grammars
- This type is recognized by Finite Automata(DFA/NFA).
- It is the least powerful.
- It has very simple rules.
- This is the Lowest level/type of Chomsky classification
- The Production Rule of this type is:
A → aB
A → a
- It is applied to Regular Languages.
- For example, S → aS | b
Type 2 : Context-Free Grammars
- This type is recognized by Pushdown Automata.
- This type is the most important for programming languages.
- In this type, LHS has a single non-terminal.
- The Production Rule for this type is:
A → γ
- It is applied to Context-Free Languages.
- For example, S → aSb | ε
Type 1 : Context-Sensitive Grammars (CSG)
- This type is recognized by Linear Bounded Automata (LBA).
- It is applied to Context-Sensitive Languages.
- The Production Rule is αAβ → αγβ.
- For example: aAb → aBBb
Type 0 : Unrestricted/Recursively Enumerable Grammars
- It is also called Phrase Structure Grammar.
- This type is applied to Recursively Enumerable Languages.
- This type is recognized by Turing Machines.
- This is the Highest level/type of Chomsky classification.
- In this type, there are no restrictions on grammar rules.
- It can generate all recursively enumerable languages.
- It is the most powerful grammar.
- It has no restriction on production rules.
- The production rule is – α → β
- For example, aAb → ba
Importance
- Chomsky Classification forms the basis of compiler design.
- It helps understand language complexity.
- It links grammar ↔ automata.
- It is the fundamental concept in TOC.
0 Comments