How Does the Chomsky Hierarchy Classify Formal Grammars?

The Chomsky hierarchy is a containment hierarchy of formal grammars introduced by linguist Noam Chomsky in 1956. It classifies formal languages and the grammars that generate them into four nested levels: Type-0, Type-1, Type-2, and Type-3. Each level is defined by specific restrictions on its production rules and corresponds to a distinct class of abstract computational machines, ranging from finite automata to Turing machines.

Formal Definition of a Grammar

In classical computing and formal language theory, a formal grammar is defined as a 4-tuple \(G = (V, \Sigma, R, S)\), where:

  • \(V\) is a finite set of non-terminal symbols.
  • \(\Sigma\) is a finite set of terminal symbols, disjoint from \(V\).
  • \(R\) is a finite set of production rules of the form \(\alpha \to \beta\), where \(\alpha \in (V \cup \Sigma)^* V (V \cup \Sigma)^*\) and \(\beta \in (V \cup \Sigma)^*\).
  • \(S \in V\) is the start symbol.

The Chomsky hierarchy categorizes grammars by placing progressively stricter constraints on the strings \(\alpha\) and \(\beta\) in the production rules.

Type-0: Unrestricted Grammars

Type-0 grammars, also known as unrestricted grammars, impose no constraints on the production rules beyond the basic requirement that the left-hand side \(\alpha\) must contain at least one non-terminal symbol. Any string of terminals and non-terminals can be replaced by any other string, including the empty string \(\varepsilon\).

  • Production rule form: \(\alpha \to \beta\), with \(\alpha \neq \varepsilon\).
  • Language class: Recursively enumerable languages.
  • Corresponding automaton: Turing machine.

Because there are no structural restrictions, Type-0 grammars have the full computational power of a Turing machine. Any language that can be recognized by an algorithm can be generated by a Type-0 grammar.

Type-1: Context-Sensitive Grammars

Type-1 grammars, or context-sensitive grammars, restrict production rules so that the length of the right-hand side is never shorter than the length of the left-hand side (with a standard exception allowing \(S \to \varepsilon\) if \(S\) does not appear on the right-hand side of any rule).

  • Production rule form: \(\alpha A \beta \to \alpha \gamma \beta\), where \(A \in V\), \(\alpha, \beta \in (V \cup \Sigma)^*\), and \(\gamma \in (V \cup \Sigma)^+\). Equivalently, \(|\alpha| \le |\beta|\) for \(\alpha \to \beta\).
  • Language class: Context-sensitive languages.
  • Corresponding automaton: Linear bounded automaton (a non-deterministic Turing machine with a tape bounded by a linear function of the input length).

In a context-sensitive grammar, a non-terminal \(A\) can only be replaced by \(\gamma\) when it appears in the specific context of \(\alpha\) and \(\beta\).

Type-2: Context-Free Grammars

Type-2 grammars, known as context-free grammars, tighten the restriction further by requiring the left-hand side of every production rule to be a single non-terminal symbol. The replacement does not depend on surrounding symbols.

  • Production rule form: \(A \to \gamma\), where \(A \in V\) and \(\gamma \in (V \cup \Sigma)^*\).
  • Language class: Context-free languages.
  • Corresponding automaton: Non-deterministic pushdown automaton.

Context-free grammars are widely used in computer science to define the syntax of programming languages and data formats, as they can express nested structures such as balanced parentheses and arithmetic expressions.

Type-3: Regular Grammars

Type-3 grammars, or regular grammars, are the most restrictive class in the hierarchy. Every production rule must have a single non-terminal on the left-hand side, and the right-hand side is limited to at most one terminal and one non-terminal, placed in a consistent order (either all right-linear or all left-linear).

  • Production rule form (right-linear): \(A \to aB\) or \(A \to a\) (and optionally \(A \to \varepsilon\)), where \(A, B \in V\) and \(a \in \Sigma\).
  • Language class: Regular languages.
  • Corresponding automaton: Finite automaton (deterministic or non-deterministic).

Regular languages are equivalent to those described by regular expressions and are commonly used for lexical analysis, pattern matching, and simple state machines.

Containment Relationship

The four levels form a strict inclusion hierarchy. Every Type-3 grammar is also a Type-2 grammar, every Type-2 grammar is a Type-1 grammar (excluding \(\varepsilon\)-productions, which can be handled separately), and every Type-1 grammar is a Type-0 grammar. In terms of language classes:

\[\text{Regular} \subset \text{Context-Free} \subset \text{Context-Sensitive} \subset \text{Recursively Enumerable}\]

As the grammar rules become less restrictive, the expressive power of the language increases, requiring more powerful computational models to recognize or parse the resulting strings.