0

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

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 解析器解析。

但是我不确定这是否正确。

4

1 回答 1

0

LR(1) 等于 DPDA。

LR(0) 与 REG、DFA 等是无法比较的。因此，如果您应该提供除一个类之外的所有类的总订单，则必须省略 LR(0)。一旦你把它排好序，四个正则形式由于不可比性而不能处于相同的总顺序。

于 2016-05-25T20:07:29.237 回答