Types of Formal Languages

Types of Formal Languages

Formal languages are essential in computer science as they provide a framework for defining and analysing the syntax and semantics of programming languages, algorithms, and computational models. There are several types of formal languages, each classified based on its generative power and the complexity of the grammar that produces them. The Chomsky hierarchy categorises these languages into four main types: Type 0, Type 1, Type 2, and Type 3.

Chomsky Hierarchy

The Chomsky hierarchy is a classification of formal languages based on their generative grammars. The hierarchy consists of four types:

• Type 0: Recursively Enumerable Languages
• Type 1: Context-Sensitive Languages
• Type 2: Context-Free Languages
• Type 3: Regular Languages

Each type has specific characteristics and is accepted by different computational models.

Type 0: Recursively Enumerable Languages

Recursively enumerable languages are the most general class in the Chomsky hierarchy. They can be recognised by a Turing machine, which is a theoretical model of computation that can simulate any algorithm. A language is recursively enumerable if there exists a Turing machine that will accept any string in the language and either reject or run forever for strings not in the language.

Example: The language of all strings of balanced parentheses, such as {(), (()), (()()), ...}, is recursively enumerable. A Turing machine can be designed to accept these strings by pushing opening parentheses onto a stack and popping them off for each closing parenthesis.

Type 1: Context-Sensitive Languages

Context-sensitive languages are more restrictive than recursively enumerable languages. They can be generated by context-sensitive grammars, where the production rules can replace strings based on their context. A language is context-sensitive if it can be recognised by a linear-bounded automaton (LBA), which is a Turing machine with limited tape space proportional to the input size.

Example: The language {a^n b^n c^n | n ≥ 1}, which consists of equal numbers of a's, b's, and c's, is context-sensitive. A context-sensitive grammar can be defined to produce this language, ensuring that the number of each symbol is equal.

Type 2: Context-Free Languages

Context-free languages are generated by context-free grammars. In these grammars, the production rules replace a single non-terminal symbol with a string of terminals and/or non-terminals. Context-free languages can be recognised by pushdown automata (PDA), which have a stack to keep track of additional information.

Example: The language of balanced parentheses is also context-free. A context-free grammar for this language can be defined as follows:

S → SS | (S) | ε

In this grammar, S is the starting symbol, and ε represents the empty string. The grammar produces all valid combinations of balanced parentheses.

Type 3: Regular Languages

Regular languages are the simplest class in the Chomsky hierarchy. They can be generated by regular grammars, which have production rules that replace a non-terminal with a terminal symbol followed by at most one non-terminal. Regular languages can be recognised by finite automata, which do not have additional memory structures like stacks.

Example: The language of all strings consisting of the letter 'a' followed by zero or more occurrences of 'b' can be represented by the regular expression a(b*). A finite automaton can be constructed to accept this language by transitioning from the start state to an accepting state upon reading 'a', and then remaining in the accepting state for any number of 'b's.

Comparing the Types of Languages

It is important to understand the relationships between the different types of formal languages. The hierarchy is structured such that:

• All regular languages are context-free.
• All context-free languages are context-sensitive.
• All context-sensitive languages are recursively enumerable.

This means that if a language is of a higher type, it can also represent all languages of the lower types.

Closure Properties

Closure properties refer to the ability of a class of languages to remain within the same class under certain operations. Here are some important closure properties for each type:

• Regular Languages: Closed under union, intersection, and complementation.
• Context-Free Languages: Closed under union and concatenation, but not under intersection or complementation.
• Context-Sensitive Languages: Closed under union, intersection, and complementation.

Applications of Formal Languages

Formal languages are widely used in various fields of computer science, including:

• Compiler design: Formal languages define the syntax and semantics of programming languages.
• Natural language processing: Formal grammars are used to model human languages.
• Automata theory: Formal languages are used to analyse the behaviour of computational models.

Understanding the different types of formal languages and their properties is crucial for building efficient algorithms and systems in these applications.

Summary

• The Chomsky hierarchy classifies formal languages into four types: recursively enumerable, context-sensitive, context-free, and regular.
• Recursively enumerable languages are recognised by Turing machines.
• Context-sensitive languages are recognised by linear-bounded automata.
• Context-free languages are recognised by pushdown automata.
• Regular languages are recognised by finite automata.

Check your understanding

1. What are the four types of formal languages in the Chomsky hierarchy?
2. Explain the difference between context-free languages and regular languages.
3. What type of automaton recognises context-sensitive languages?
4. List two applications of formal languages in computer science.