Skip to content

Extended Chomsky Hierarchy

Classical, 1956

TypeLanguageAutomatonProduction rules
3regularDFAAa;AaB;ABa;A \rightarrow a; A \rightarrow aB; A \rightarrow Ba;
2context-freePDAAαA \rightarrow \alpha
1context-sensitiveLBAαAβαγβ\alpha A\beta \rightarrow \alpha \gamma \beta
0recursively enumerableTMγα\gamma \rightarrow \alpha (γ\gamma non-empty)

Robins

Extended Chomsky Hierarchy

Diagram taken here.

On multiple context-free grammars, 1990

Diagram taken from On multiple context-free grammars, 1990

Boolean grammars, 2004

Diagram taken from Boolean grammars, 2004

RegLinCFCFLinConjConjBoolCS
Closure properties
\cup+++++++
\cap+--++++
negation+--+?++
concatenation \cdot+-+-+++
Kleene star+-+-+++
hh+++----
h1h^{-1}+++++?+
Decision problems
Membership+++++++
Emptiness+++----
Equivalence+------
Compl. of recognition
Lower boundNLNLPPPPSPACE
Upper boundNLNC2NC^2PPPPSPACE
Known algorithmnnn2n^2n2.376n^{2.376}n2n^2n3n^3n3n^3CnC^n

Quick Grammar Type Recognition: Concepts and Techniques, 2007

Diagram taken from Quick Grammar Type Recognition: Concepts and Techniques, 2007

The Word Problem in the Chomsky Hierarchy, 2010

Diagram taken from The Word Problem in the Chomsky Hierarchy, 2010

String Turing Machines, 2010

TypeCursor actions string TM (1)Algebra
3DKleene algebra (KA)
2R, DKA with least fixed-point operator (μ)
1L, R, D?
0I, L, R, D?

(1) A Characterization of the Chomsky Hierarchy by String Turing Machines. Cursor actions: I - insert, D - delete, R - right, L - left

Posts lattice for language equations, 2015

Diagram taken from On language equations with concatenation and various sets of boolean operations, 2015

When Input-Driven Pushdown Automata Meet Reversiblity, 2016

Diagram taken from When Input-Driven Pushdown Automata Meet Reversiblity, 2016

Input-Driven Double-Head Pushdown Automata, 2017

Diagram taken from Input-Driven Double-Head Pushdown Automata, 2017

Hardest languages for conjunctive and Boolean grammars, 2019

Diagram taken from The hardest language for grammars with context operators, 2019

The hardest language for grammars with context operators, 2021

Diagram taken from The hardest language for grammars with context operators, 2021

On the Expressive Power of Regular Expressions with Backreferences, 2023

Diagram taken from On the Expressive Power of Regular Expressions with Backreferences, 2023

See also On Lookaheads in Regular Expressions with Backreferences, 2023

Neural Networks and the Chomsky Hierarchy, 2023

Diagram taken from Neural Networks and the Chomsky Hierarchy, 2023

Regular Expressions with Backreferences on Multiple Context-Free Languages, and the Closed-Star Condition, 2024

Diagram taken from Regular Expressions with Backreferences on Multiple Context-Free Languages, and the Closed-Star Condition, 2024

Other