Chomsky Hierarchy
Understanding the four types of formal grammars and their corresponding languages and automata
Chomsky Hierarchy
The Chomsky Hierarchy is a classification of formal grammars and languages that provides a framework for understanding computational power and expressiveness.
Theory & Concepts
Definition:
The Chomsky Hierarchy classifies formal grammars into four types (0-3) based on their rule restrictions, with corresponding languages and automata models.
Key Points:
- Type 0: Unrestricted grammars, recognized by Turing machines
- Type 1: Context-sensitive grammars, recognized by linear bounded automata
- Type 2: Context-free grammars, recognized by pushdown automata
- Type 3: Regular grammars, recognized by finite automata
Applications:
- Compiler design and parsing algorithms
- Natural language processing
- Formal verification of systems
- Understanding computational complexity
University Guidelines
Exam Weightage
8-10 marks MarksSyllabus Coverage:
- Chomsky hierarchy of grammars and languages
- Regular, context-free, context-sensitive, and recursive languages
- Relationship between grammar types and automata
- Limitations of each language class
Common Questions:
- Explain the Chomsky hierarchy with examples
- Compare and contrast the four types of grammars
- Explain the relationship between grammars and corresponding automata
- Classify given grammars into appropriate Chomsky hierarchy types
Exam Tips:
Know the formal definitions of each grammar type
Understand the containment relationship between language classes
Be able to provide concrete examples for each grammar type
Remember that each grammar type corresponds to a specific automaton model
Algorithm Details
Varies by grammar type
Time Complexity
Varies by grammar type
Space Complexity
Algorithm Steps:
- 1Identify the grammar rules
- 2Check the form of productions against the constraints of each type
- 3Type 0: No restrictions on productions
- 4Type 1: Productions can't decrease length (context-sensitive)
- 5Type 2: Left side must be a single non-terminal (context-free)
- 6Type 3: Right side must be a terminal optionally followed by a non-terminal (regular)
Chomsky Hierarchy
Type 0: Recursively Enumerable
Unrestricted grammar; accepted by Turing machines
subset of
Type 1: Context-Sensitive
Accepted by linear bounded automata
subset of
Type 2: Context-Free
Accepted by pushdown automata
subset of
Type 3: Regular
Accepted by finite automata
Complexity and Power
Computational Power:
Less PowerfulMore Powerful
RegularContext-FreeContext-SensitiveRecursive
Recognition Complexity:
Less ComplexMore Complex
O(n)O(n³)PSPACEUndecidable
Language Examples
L = {a^n | n ≥ 0}
Any number of a's
Type 3
L = {a^n b^n | n ≥ 1}
Equal number of a's followed by b's
Type 2
L = {a^n b^n c^n | n ≥ 1}
Equal number of a's, b's, and c's
Type 1
L = {ww | w ∈ {a,b}*}
Any string concatenated with itself
Type 1
Halting Problem language
The set of all Turing machines that halt on empty input
Type 0
Hierarchy Relationships
Containment
Each language class is a proper subset of the classes above it:
Regular ⊂ Context-Free ⊂ Context-Sensitive ⊂ Recursive ⊂ Recursively Enumerable
This means that every regular language is context-free, but not every context-free language is regular, and so on.
Closure Properties
- Regular languages: Union, intersection, complement
- Context-free: Union, concatenation, Kleene star
- Not closed: Context-free languages under intersection
Decision Problems
- Regular: Membership, emptiness, equivalence
- Context-free: Membership, emptiness
- ✗Context-free: Equivalence (undecidable)
Practical Significance
- Regular languages: Used for lexical analysis in compilers (tokens)
- Context-free languages: Used for syntax analysis (parsing) in compilers
- Context-sensitive and beyond: Natural languages and complex systems modeling