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)

See also A Characterization of the Chomsky Hierarchy by String Turing Machines

Robins

Extended Chomsky Hierarchy

Diagram taken here.

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

Posts lattice for language equations, 2015

Extended Chomsky Hierarchy

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

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

Other