Extended Chomsky Hierarchy

Classical, 1956

Type	Language	Automaton	Production rules
3	regular	DFA	$A \rightarrow a; A \rightarrow aB; A \rightarrow Ba;$
2	context-free	PDA	$A \rightarrow \alpha$
1	context-sensitive	LBA	$\alpha A\beta \rightarrow \alpha \gamma \beta$
0	recursively enumerable	TM	$\gamma \rightarrow \alpha$ ($\gamma$ non-empty)

Robins

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 ↗

	Reg	LinCF	CF	LinConj	Conj	Bool	CS
Closure properties
$\cup$	+	+	+	+	+	+	+
$\cap$	+	-	-	+	+	+	+
negation	+	-	-	+	?	+	+
concatenation $\cdot$	+	-	+	-	+	+	+
Kleene star	+	-	+	-	+	+	+
$h$	+	+	+	-	-	-	-
$h^{-1}$	+	+	+	+	+	?	+
Decision problems
Membership	+	+	+	+	+	+	+
Emptiness	+	+	+	-	-	-	-
Equivalence	+	-	-	-	-	-	-
Compl. of recognition
Lower bound		NL	NL	P	P	P	PSPACE
Upper bound		NL	$NC^2$	P	P	P	PSPACE
Known algorithm	$n$	$n^2$	$n^{2.376}$	$n^2$	$n^3$	$n^3$	$C^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

Type	Cursor actions string TM (1)	Algebra
3	D	Kleene algebra (KA)
2	R, D	KA with least fixed-point operator (μ) ↗
1	L, R, D	?
0	I, 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

• Formal language theory: refining the Chomsky hierarchy, 2012 ↗