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)

Other

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

Robins

Diagram taken here.

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$

Posts lattice for language equations, 2015

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

• Formal language theory: refining the Chomsky hierarchy, 2012