0

私はこの形式主義のリストを持っており、表現力に従って並べる必要があります。また、そのうちの 1 つは実際には属していません。

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 文法を削除しました。これは、LR パーサーで解析できるように CFG を記述する方法にすぎないためです。

ただし、これが正しいかどうかはわかりません。

4

1 に答える 1

0

LR(1) は DPDA と同じです。

LR(0) は REG や DFA などとは比較にならないものです。したがって、1 つを除くすべてのクラスで合計注文を提供することになっている場合は、LR(0) を除外する必要があります。順番に並べるとすぐに、4 つの正規の形式は、比較不可能なため、合計で同じ順番になることはありません。

于 2016-05-25T20:07:29.237 に答える