Hierarchy Levels
COS3701 - Theoretical Computer Science III · The Chomsky Hierarchy
Hierarchy Levels
The Chomsky hierarchy is a classification of formal languages based on their generative power. This hierarchy consists of four levels: Type 0, Type 1, Type 2, and Type 3. Each type corresponds to a different class of languages and a different class of automata. Understanding these levels is crucial for studying the theory of computation.
Type 0: Recursively Enumerable Languages
Type 0 languages are the most powerful in the Chomsky hierarchy. They are also known as recursively enumerable languages. These languages can be recognized by a Turing machine. A Turing machine is a theoretical model of computation that can simulate any algorithm. It has an infinite tape and can read and write symbols on that tape.
Examples of Type 0 languages include:
- The set of all strings that can be generated by a context-free grammar.
- The set of all strings that can be accepted by a non-deterministic Turing machine.
Remember: A language is recursively enumerable if there exists a Turing machine that will accept any string in the language, but may not halt for strings not in the language.
Type 1: Context-Free Languages
Type 1 languages are known as context-sensitive languages. They can be generated by context-sensitive grammars and recognized by linear-bounded automata. A linear-bounded automaton is a Turing machine with tape space limited to a linear function of the input size.
Examples of Type 1 languages include:
- The language of all strings of the form a^n b^n c^n, where n ≥ 1.
- The language of all palindromes over a given alphabet.
Remember: A language is context-sensitive if it can be generated by a context-sensitive grammar that adheres to the constraints of the Chomsky hierarchy.
Type 2: Context-Free Languages
Type 2 languages are generated by context-free grammars and recognized by pushdown automata. A pushdown automaton is a type of automaton that uses a stack to keep track of additional information.
Examples of Type 2 languages include:
- The language of balanced parentheses.
- The language generated by the grammar S → aSb | ε, which generates strings of the form a^n b^n.
Remember: A language is context-free if it can be generated by a context-free grammar, which allows for recursive productions.
Type 3: Regular Languages
Type 3 languages are the simplest in the Chomsky hierarchy. They can be generated by regular grammars and recognized by finite automata. A finite automaton is a computational model that processes input strings and determines whether they belong to a particular language.
Examples of Type 3 languages include:
- The language of all strings consisting of a's and b's that contain an even number of a's.
- The language defined by the regular expression (a|b)*, which represents all strings made up of a's and b's.
Remember: A language is regular if it can be described by a regular expression or accepted by a finite automaton.
Comparison of the Levels
To summarise the Chomsky hierarchy:
| Type | Language Class | Grammar Type | Automaton Type |
|---|---|---|---|
| Type 0 | Recursively Enumerable | Unrestricted Grammar | Turing Machine |
| Type 1 | Context-Sensitive | Context-Sensitive Grammar | Linear-Bounded Automaton |
| Type 2 | Context-Free | Context-Free Grammar | Pushdown Automaton |
| Type 3 | Regular | Regular Grammar | Finite Automaton |
This table shows the increasing power of languages as you move from Type 3 to Type 0. Each type of language can be recognised by a corresponding type of automaton, which reflects its complexity.
Applications of the Chomsky Hierarchy
The Chomsky hierarchy is not just a theoretical construct. It has practical applications in various fields, including:
- Programming languages: Understanding the type of grammar a programming language uses can help in designing compilers.
- Natural language processing: The hierarchy helps in modelling the syntax of natural languages.
- Automata theory: It provides a framework for understanding the capabilities and limitations of different computational models.
Tip: Familiarise yourself with examples of each type of language, as this will help you understand the practical implications of the Chomsky hierarchy.
Common Mistakes
Watch out: Do not confuse context-free languages with context-sensitive languages. Context-free languages are a subset of context-sensitive languages, but they are not the same.
Summary
- The Chomsky hierarchy consists of four levels: Type 0, Type 1, Type 2, and Type 3.
- Type 0 languages are recursively enumerable and recognised by Turing machines.
- Type 1 languages are context-sensitive and recognised by linear-bounded automata.
- Type 2 languages are context-free and recognised by pushdown automata.
- Type 3 languages are regular and recognised by finite automata.
Check your understanding
- What are the four levels of the Chomsky hierarchy?
- What type of automaton recognises context-free languages?
- Give an example of a Type 1 language.
- Explain the difference between Type 2 and Type 3 languages.