比较FA，PDA和TM的非确定性和确定性表达能力

Question

我很困惑，也无法在网上找到答案，但在表达能力方面，。

非确定性FA，PDA，TM

NFA < NPDA < NTM

确定性FA，PDA，TM：这是我感到困惑的地方

DFA < PDA < TM?

总的来说：？

DFA = NFA = e-NFA = RE < DPDA < NPDA = NCFL = DCFL < NTM = DTM? 

请纠正我或我是否正确？

Answer 1

DFA <PDA <TM是正确的。

请记住，DFA = NFA = RegEx电源，每个NFA都可以转换为DFA，可以转换为RegEx，反之亦然。

上下文免费语言有点不同。 PDA≠NPDA。您可以为上下文无关语言的子集构建PDA，但您可以为任何上下文无关语言构建NPDA。

图灵机，确定性和非确定性，同样强大。请记住，您可以使用单个磁带DTM模拟任何NTM。

所以在整体上，DFA = NFA = e-NFA = RE <DPDA <NPDA = NCFL = DCFL <NTM = DTM是正确的直觉。