# 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) |

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

## 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