What is the Chomsky hierarchy of formal languages?

The Chomsky hierarchy of formal languages is a classification system that categorizes formal languages into four levels based on their generative power and the types of grammars that can generate them. The four levels are:

1. Type 0 (Unrestricted Grammar): This level includes all possible formal languages and grammars. These languages can be generated by Turing machines and have no restrictions on the production rules.

2. Type 1 (Context-Sensitive Grammar): This level includes languages that can be generated by context-sensitive grammars. The production rules in these grammars allow for limited modifications of the strings, but the modifications must preserve the context of the surrounding symbols.

3. Type 2 (Context-Free Grammar): This level includes languages that can be generated by context-free grammars. The production rules in these grammars are not dependent on the context and can be applied to any non-terminal symbol.

4. Type 3 (Regular Grammar): This level includes languages that can be generated by regular grammars. The production rules in these grammars are the simplest and most restricted, allowing for only a single non-terminal symbol on the left-hand side and a terminal or empty string on the right-hand side.

The Chomsky hierarchy provides a framework for understanding the complexity and expressive power of different types of formal languages.