1.3 Chomsky hierarchy and language classes

The Chomsky hierarchy organizes languages based on grammar complexity. It includes four levels: regular, context-free, context-sensitive, and recursively enumerable. Each level builds on the previous, offering more expressive power but requiring more complex computational models.

Understanding these language classes is crucial for grasping formal language theory. Regular and context-free languages are widely used in practice, while context-sensitive and recursively enumerable languages demonstrate the theoretical limits of computation and language processing.

Chomsky Hierarchy Levels

Introduction to the Chomsky Hierarchy

Top images from around the web for Introduction to the Chomsky Hierarchy

• 

  Chomsky Hierarchy View original

  Is this image relevant?

• 

  Chomsky Hierarchy View original

  Is this image relevant?

• 

  Chomsky Hierarchy View original

  Is this image relevant?

• 

  Chomsky Hierarchy View original

  Is this image relevant?

• 

  Chomsky Hierarchy View original

  Is this image relevant?

1 of 3

Top images from around the web for Introduction to the Chomsky Hierarchy

• 

  Chomsky Hierarchy View original

  Is this image relevant?

• 

  Chomsky Hierarchy View original

  Is this image relevant?

• 

  Chomsky Hierarchy View original

  Is this image relevant?

• 

  Chomsky Hierarchy View original

  Is this image relevant?

• 

  Chomsky Hierarchy View original

  Is this image relevant?

1 of 3

• The Chomsky hierarchy classifies formal languages based on the complexity of the grammars that generate them
• Consists of four levels, each corresponding to a specific type of grammar and the languages they generate (regular, context-free, context-sensitive, and recursively enumerable)
• The hierarchy is inclusive, meaning each level includes all the languages from the levels below it
• Named after the linguist and computer scientist Noam Chomsky, who introduced the concept in the 1950s

Properties of the Chomsky Hierarchy

• The language classes in the Chomsky hierarchy form a strict inclusion hierarchy, with each class properly containing the classes below it: recursively enumerable ⊃ context-sensitive ⊃ context-free ⊃ regular
• The higher the level in the hierarchy, the more expressive and computationally powerful the languages become, but also the more complex and less efficient the corresponding grammars and automata are
• Regular and context-free languages are decidable, meaning there exist algorithms to determine whether a given string belongs to the language
• Context-sensitive and recursively enumerable languages are generally undecidable

Language Classes: Regular vs Context-Free vs Context-Sensitive vs Recursively Enumerable

Regular Languages (Type-3)

• The simplest and most restrictive class, generated by regular grammars or recognized by finite automata
• Cannot handle nested or recursive structures
• Examples: the set of all strings over {a, b} with an even number of a's, the set of all strings over {0, 1} that end with 01, or the set of all strings representing valid email addresses

Context-Free Languages (Type-2)

• More expressive than regular languages, generated by context-free grammars or recognized by pushdown automata
• Can handle nested structures but not complex dependencies
• Examples: the set of all palindromes over {a, b}, the set of all properly nested parentheses, or the set of all strings of the form $a^n b^n$ (where $n \geq 0$)

Context-Sensitive Languages (Type-1)

• More powerful than context-free languages, generated by context-sensitive grammars or recognized by linear-bounded automata
• Can handle complex dependencies and structures
• Examples: the set of all strings of the form $a^n b^n c^n$ (where $n \geq 0$), or the set of all strings over {a, b, c} where the number of a's, b's, and c's are equal

Recursively Enumerable Languages (Type-0)

• The most expressive and least restrictive class, generated by unrestricted grammars or recognized by Turing machines
• Include all possible languages that can be generated by a formal grammar
• Examples: the set of all valid C++ programs, the set of all strings that represent a valid encoding of a Turing machine, or the set of all strings that can be generated by a phrase-structure grammar

Examples of Language Classes

Regular Language Examples

• The set of all binary strings with an odd number of 1's (01, 001, 1011)
• The set of all strings over {a, b} that do not contain the substring "aa" (b, ab, bab, abab)

Context-Free Language Examples

• The set of all strings of the form $a^i b^j c^k$ where $i = j$ or $j = k$ (abc, aabbcc, aaabbbccc)
• The set of all strings over {a, b} that have an equal number of a's and b's (ab, aabb, aaabbb)

Context-Sensitive Language Examples

• The set of all strings over {a, b, c} where the number of a's is equal to the number of b's plus the number of c's ($a^{n+m} b^n c^m$, where $n, m \geq 0$) (a, abc, aabbcc, aaabbbccc)
• The set of all strings over {a, b} of the form $ww$, where $w$ is any string over {a, b} (aa, bb, abab, aabaab)

Recursively Enumerable Language Examples

• The set of all strings that represent a valid encoding of a halting Turing machine
• The set of all strings that can be generated by a context-sensitive grammar augmented with the ability to check for the presence or absence of certain substrings

Relationships Between Language Classes

Strict Inclusion Hierarchy

• Each class properly contains the classes below it: recursively enumerable ⊃ context-sensitive ⊃ context-free ⊃ regular
• This means that every regular language is also context-free, every context-free language is also context-sensitive, and every context-sensitive language is also recursively enumerable

The Pumping Lemma

• The pumping lemma is a tool used to prove that a language does not belong to a specific class in the hierarchy
• There are different versions of the pumping lemma for regular, context-free, and context-sensitive languages
• The pumping lemma provides a necessary condition for a language to belong to a specific class, and if a language violates this condition, it cannot belong to that class or any class below it in the hierarchy