哪些形式主义不属于，哪些更强大/平等

Question

我有这个形式主义的清单，我需要根据它们的表达能力对它们进行排序，而且其中一个并不真正属于它们。

Context-free Grammar(CFG)
Deterministic Finite Automata(DFA)
Deterministic Pushdown Automata(DPDA)
LR(0) Grammar
LR(1) Grammar
Nondeterministic Finite Automata(NFA)
Nondeterministic Finite Automata with epsilon transitions(NFAe)
Nondeterministic Turing MAchines(NTM)
Pushdown Automata(PDA)
Regular expressions(reg.exp)
Turing Machines(TM)
Turing MAchines with twi heads(TM2h)

我已经通过以下方式订购了它们：

1. NFAe, NFA, DFA, reg.exp
2. DPDA
3. PDA, CFG
4. TM, TM2h, NTM

其中4中的那些是最强大的。我删除了LR语法，因为它们只是一种编写CFG的方式，以便它们可以被LR解析器解析。

然而，我不确定这是否正确。

Answer 1

LR(1)等于DPDA。

LR(0)无法与REG、DFA等相媲美。因此，如果您需要提供除一个类之外的所有类的总顺序，则必须省略LR(0)。一旦你把它放在顺序中，由于不可比较性，四种常规形式不可能处于相同的总顺序中。