1.3. The Chomsky Hierarchy

The Chomsky hierarchy classifies formal languages — and the automata that recognise them — into four nested families. Each level is a strict restriction of the one above it: a more constrained grammar, a less powerful machine, a smaller class of languages.

Type	Grammar	Automaton	Language family
0	Unrestricted	Turing Machine	Recursively enumerable
1	Context-sensitive	Linear Bounded Automaton	Context-sensitive
2	Context-free	Pushdown Automaton	Context-free
3	Regular	Finite State Automaton	Regular

This section covers the theoretical foundations of each level and its implementation in fsm-tools.

• 1.3.1. Alphabet, grammar and Language
  • 1.3.1.1. Alphabet
  • 1.3.1.2. Terminals and Non-terminals
  • 1.3.1.3. Grammar
  • 1.3.1.4. Language
• 1.3.2. The Kleene Star (Kleene closure)
  • 1.3.2.1. Formal Definition
  • 1.3.2.2. Kleene closure
  • 1.3.2.3. Example
  • 1.3.2.4. Differences with \(+\) operator
• 1.3.3. The Chomsky-Schützenberger Hierarchy
  • 1.3.3.1. Type 0 - Unrestricted Grammars
  • 1.3.3.2. Type 1 - Context-Sensitive Grammars
  • 1.3.3.3. Type 2 - Context-Free Grammars
  • 1.3.3.4. Type 3 - Regular Grammars
• 1.3.4. Automata in fsm-tools
  • 1.3.4.1. TuringMachine — Type 0
  • 1.3.4.2. LinearBoundedAutomaton — Type 1
  • 1.3.4.3. PushdownAutomaton — Type 2
  • 1.3.4.4. FiniteStateAutomaton — Type 3