Extended Chomsky Hierarchy
Classical, 1956
Type | Language | Automaton | Production rules |
---|---|---|---|
3 | regular | DFA | |
2 | context-free | PDA | |
1 | context-sensitive | LBA | |
0 | recursively enumerable | TM | ( 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
- insertD
- deleteR
- rightL
- left
Robins
Diagram taken here.
Boolean grammars, 2004
Diagram taken from Boolean grammars, 2004
Reg | LinCF | CF | LinConj | Conj | Bool | CS | |
---|---|---|---|---|---|---|---|
Closure properties | |||||||
+ | + | + | + | + | + | + | |
+ | - | - | + | + | + | + | |
negation | + | - | - | + | ? | + | + |
concatenation | + | - | + | - | + | + | + |
Kleene star | + | - | + | - | + | + | + |
+ | + | + | - | - | - | - | |
+ | + | + | + | + | ? | + | |
Decision problems | |||||||
Membership | + | + | + | + | + | + | + |
Emptiness | + | + | + | - | - | - | - |
Equivalence | + | - | - | - | - | - | - |
Compl. of recognition | |||||||
Lower bound | NL | NL | P | P | P | PSPACE | |
Upper bound | NL | P | P | P | PSPACE | ||
Known algorithm |
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