Chomsky's hierarchy of grammars

Chomsky's Hierarchy of Grammars

Chomsky's hierarchy is a classification of formal grammars into four types based on their generative power (the complexity of the languages they can generate). These grammar types are structured from least powerful to most powerful. The hierarchy was introduced by Noam Chomsky in 1956 and has become a central concept in formal language theory, computational theory, and linguistics.

The four levels in Chomsky’s hierarchy are:

1. Type 3: Regular Grammars
2. Type 2: Context-Free Grammars (CFGs)
3. Type 1: Context-Sensitive Grammars (CSGs)
4. Type 0: Unrestricted Grammars

Each type of grammar in the hierarchy can generate a specific class of languages, and each level includes the grammars of the levels below it (i.e., regular grammars are a subset of context-free grammars, context-free grammars are a subset of context-sensitive grammars, and so on). The hierarchy helps in understanding how the complexity of languages relates to the computational power required to process them.

Type 3: Regular Grammars

• Definition: Regular grammars are the simplest class of grammars. They can generate regular languages, which are the languages that can be recognized by a finite automaton.

• Production Rules: The production rules in a regular grammar are of the form:

  • $A \to aB$
  • $A \to a$
  • $A \to \epsilon$

  Where:

  • $A$ and $B$ are non-terminal symbols,
  • $a$ is a terminal symbol,
  • $\epsilon$ represents the empty string.

• Characteristics:

  • Regular grammars can be represented by finite automata (deterministic or non-deterministic).
  • Regular languages can be described using regular expressions.
  • Regular languages are closed under operations such as union, intersection, and Kleene star.

• Examples: Languages like:

  • $L = \{ a^n \mid n \geq 1 \}$, which is the set of all strings of "a's".
  • $L = \{ a^n b^n \mid n \geq 0 \}$, which is the set of strings consisting of some number of "a's" followed by an equal number of "b's".

Type 2: Context-Free Grammars (CFGs)

• Definition: Context-free grammars (CFGs) generate context-free languages (CFLs), which can be recognized by pushdown automata (PDA), machines that have a stack for memory.

• Production Rules: The production rules in a context-free grammar are of the form:

  • $A \to \alpha$, where $A$ is a non-terminal symbol and $\alpha$ is a string of terminals and non-terminals.

  A key restriction here is that the left-hand side of every production consists of a single non-terminal symbol.

• Characteristics:

  • Context-free languages can be parsed efficiently using recursive descent parsers and LL or LR parsers.
  • Context-free languages are closed under operations such as union, concatenation, and Kleene star.
  • CFGs can describe many programming languages and mathematical expressions.

• Examples:

  • $L = \{ a^n b^n \mid n \geq 0 \}$, which is the set of strings consisting of an equal number of "a's" followed by "b's".
  • Arithmetic expressions, which can be described using context-free grammars.

Type 1: Context-Sensitive Grammars (CSGs)

• Definition: Context-sensitive grammars generate context-sensitive languages, which are more powerful than context-free languages. They can be recognized by linear bounded automata (LBA), a Turing machine with limited space.

• Production Rules: The production rules in a context-sensitive grammar are of the form:

  • $\alpha A \beta \to \alpha \gamma \beta$, where $\alpha$, $\beta$, and $\gamma$ are strings of terminals and non-terminals, and the length of $\gamma$ is greater than or equal to the length of $A$.

  The left-hand side of the rule may involve more than one non-terminal symbol, and the key feature is that no production rule can reduce the size of the string, meaning the length of the right-hand side must be at least as long as the left-hand side.

• Characteristics:

  • Context-sensitive languages are decidable, and the problem of membership in a context-sensitive language is solvable by a linear bounded automaton.
  • Context-sensitive grammars can describe more complex syntactic structures that cannot be handled by context-free grammars.
  • Context-sensitive languages are closed under intersection, but not under union.

• Examples:

  • $L = \{ a^n b^n c^n \mid n \geq 1 \}$, which is the set of strings where the number of "a's", "b's", and "c's" are all equal.
  • This class includes languages where the context in which a symbol appears affects how it is rewritten.

Type 0: Unrestricted Grammars

• Definition: Unrestricted grammars are the most general class of grammars. They can generate recursively enumerable languages, which are the class of languages that can be recognized by a Turing machine.

• Production Rules: The production rules in an unrestricted grammar can be of the form:

  • $\alpha \to \beta$, where $\alpha$ and $\beta$ are strings of non-terminals and terminals, and there are no restrictions on the form of $\alpha$ and $\beta$. The left-hand side can be any string of symbols, and the right-hand side can be any string as long as it’s not empty.

• Characteristics:

  • Unrestricted grammars are the most powerful class in the Chomsky hierarchy and can generate any language that a Turing machine can recognize.
  • They are not necessarily decidable, as some languages generated by unrestricted grammars may lead to undecidable problems, like the halting problem.
  • Unrestricted grammars are closed under intersection and union.

• Examples:

  • Recursively enumerable languages, which include languages that may not have a finite decision process (i.e., a Turing machine may not halt for all inputs).
  • Any language that a Turing machine can compute can be described by an unrestricted grammar.

Chomsky Hierarchy Summary

Conclusion

Chomsky's hierarchy provides a clear structure for understanding the complexity of formal languages and their recognition by computational models. From regular languages (which can be recognized by finite automata) to recursively enumerable languages (which can be recognized by Turing machines), the hierarchy helps define the computational limits of different classes of languages. Each level in the hierarchy offers more expressive power but also increases the complexity of language recognition, with Type 0 grammars being the most general and powerful.