Properties of Each Level

COS3701 - Theoretical Computer Science III · The Chomsky Hierarchy

Properties of Each Level

The Chomsky hierarchy classifies languages into four levels based on their generative power. These levels are regular languages, context-free languages, context-sensitive languages, and recursively enumerable languages. Each level has distinct properties and capabilities.

Regular Languages

Regular languages are the simplest type of languages in the Chomsky hierarchy. They can be described by regular expressions and accepted by finite automata. Regular languages have the following properties:

Can be recognised by deterministic finite automata (DFA) and non-deterministic finite automata (NFA).
Closed under union, concatenation, and Kleene star operations.
Cannot represent nested structures.

For example, the language of all strings over the alphabet {a, b} that contain an even number of a's can be represented by the regular expression (b*ab*a)*. This expression indicates that any combination of b's can occur around pairs of a's.

Remember: Regular languages cannot count or remember past symbols, which limits their expressive power.

Context-Free Languages

Context-free languages (CFLs) are more powerful than regular languages. They can be generated by context-free grammars and accepted by pushdown automata (PDA). The properties of context-free languages include:

Can represent nested structures, such as parentheses in mathematical expressions.
Closed under union, concatenation, and Kleene star operations.
Not closed under intersection or complement.

An example of a context-free language is the set of balanced parentheses, which can be defined by the grammar:

S → SS | (S) | ε

Here, S represents a balanced string of parentheses. The empty string (ε) is also part of the language.

Tip: To determine if a language is context-free, try to find a context-free grammar that generates it.

Context-Sensitive Languages

Context-sensitive languages (CSLs) are more powerful than context-free languages. They can be generated by context-sensitive grammars and accepted by linear-bounded automata (LBA). The properties of context-sensitive languages include:

Can represent more complex structures than context-free languages.
Closed under union, concatenation, and intersection.
Not closed under complement.

An example of a context-sensitive language is the language L = {a^n b^n c^n | n ≥ 1}, which consists of equal numbers of a's, b's, and c's. This language cannot be generated by a context-free grammar.

S → aSbc | abc

This grammar generates strings with equal numbers of a's, b's, and c's by ensuring that for every a added, a corresponding b and c are added.

Watch out: Many students confuse context-free and context-sensitive languages. Remember that context-sensitive languages can express relationships that context-free languages cannot.

Recursively Enumerable Languages

Recursively enumerable languages (RELs) are the most powerful type of languages in the Chomsky hierarchy. They can be generated by Turing machines. The properties of recursively enumerable languages include:

Can represent any computation that can be performed by a Turing machine.
Not closed under intersection or complement.
Can be undecidable, meaning there is no algorithm that can determine membership for all strings.

An example of a recursively enumerable language is the set of all Turing machine descriptions that halt on a given input. This language is undecidable, as per the Halting Problem.

Remember: While all regular languages are context-free, and all context-free languages are context-sensitive, not all context-sensitive languages are recursively enumerable.

Comparison of Language Classes

The Chomsky hierarchy shows a clear relationship between the different types of languages:

Regular languages are a subset of context-free languages.
Context-free languages are a subset of context-sensitive languages.
Context-sensitive languages are a subset of recursively enumerable languages.

This relationship can be visualised as follows:

Language Class	Examples	Recognised By
Regular Languages	Strings with even a's	DFA, NFA
Context-Free Languages	Balanced parentheses	PDA
Context-Sensitive Languages	a^n b^n c^n	LBA
Recursively Enumerable Languages	Halting problem	Turing Machine

Conclusion

Understanding the properties of each level in the Chomsky hierarchy is essential for studying theoretical computer science. Each level has distinct characteristics that determine the types of languages that can be generated and recognised. Regular languages are the simplest, followed by context-free languages, context-sensitive languages, and finally recursively enumerable languages, which encompass the most complex structures.

Summary

Regular languages are recognised by finite automata and cannot represent nested structures.
Context-free languages can represent nested structures and are recognised by pushdown automata.
Context-sensitive languages are more powerful than context-free languages and are recognised by linear-bounded automata.
Recursively enumerable languages are the most powerful and can represent any computation performed by Turing machines.

Check your understanding

What are the main properties of regular languages?
Give an example of a context-free language and its grammar.
Explain the difference between context-sensitive and recursively enumerable languages.
What is the significance of the Chomsky hierarchy in theoretical computer science?