automata - SCXML 描述了什么样的自动机？

Question

SCXML 的局限性是否与确定性有限自动机/确定性有限状态机相同，或者 SCXML 的功能是否可以更好地被其他抽象机器/自动机捕获？例如，SCXML 能否被认为足以描述下推自动机或图灵机？

Answer 1

如果没有数据模型，您可以将每个 SCXML 文档映射到等效的 DFA。在将 NFA 转换为 DFA 时，您将使用 powerset 构造。但是对于每一个实际目的来说，jbeard4 都是正确的，只要你有一个图灵完备的数据模型，SCXML 就是图灵完备的。

更新： 我必须纠正我这个问题。SCXML，即使没有任何数据模型，也已经是图灵完备的了！使用内部队列作为 FIFO，您可以对确定性队列自动机 (DQA) 进行建模，它相当于图灵机。因此，SCXML 是图灵完备的。

Answer 2

实际上，SCXML 是图灵完备的，因为它可以使用脚本标签来执行任意图灵完备的代码。