有限状态自动机作为（编程）语言接受器

Question

我知道 FSA 如何接受字符串“nice”（如维基百科页面所示），但是 FSA 接受的语言怎么可能是编程语言呢？

是这样吗？假设我有一个字母表 A={1,2,+,-} 和语言 L={1+1,1+2,​​1-1,1-2} 那么我的 FSA 看起来像这样；

-->[1]--1-->[2]--+-->[3]--1-->[[5]]
             |        |
             -        2-->[[6]]
             |
             v
            [4]--1-->[[7]]
             |
             2-->[[8]]

当我到达接受状态 5、6、7、8 时，我知道该值应该是什么，因此我定义了一种编程语言？？？

如果我将其扩展为具有嵌套的 FSA，那么我可以计算像“1plus2”和“sqrt(9)”这样的字符串。

这种想法正确吗？

Answer 1

不，这不太正确。要理解 FSA 与计算的关系，您需要采用更一般的计算视图。

一般来说，计算就是获取输入并产生输出。现在，让我们关注一类可以计算答案的问题：决策问题，其中输出仅限于“是”或“否”。让我们进一步将我们正在讨论的问题类型限制为那些输入为字符串（例如“nice”）的决策问题。这些正是 FSA 可以用来回答的问题（但它们无法回答所有问题！）。

因此，FSA 可以回答以下形式的（一些）问题：字符串 X 是否拥有属性 Y？例如，“该字符串是已知的有限字符串集中之一吗？”、“该字符串是奇数的二进制表示形式吗？”、“该字符串是否有 'cat' 作为子字符串？”。这些都可以由FSA来解答。

你的问题——比如 1+1——不是一个决策问题。不过，您可以将其作为一个决策问题，如下所示：“我的字符串是否具有 'x+y=z' 形式，其中 x、y 和 z 是整数 X、Y 和 Z 的十进制表示形式，并且 X + Y = Z ？”这个问题以及许多类似的问题无法使用 FSA 来回答。

存在更强大的状态机；它们不是“有限的”。示例包括下推自动机 (PDA)、线性有界自动机 (LBA) 和图灵机 (TM)。存在一些“字符串 X 是否拥有属性 Y？”形式的决策问题。即使是图灵机这种已知最强大的自动机也无法回答这个问题。停止问题给出了一个例子：“给定‘x(y)’，其中 x 是一个程序，y 是程序的输入，当传递输入 y 时，X 表示的程序是否停止？”。在一般情况下，没有 TM（即没有算法）可以回答这个问题。

你能写一个 FSA 来回答“在我定义的语言中，字符串 xa 在语法上是有效的字符串吗？”这个问题。当然，这取决于您的语言规则。 FSA 可以识别“Number + Number + ... + Number”形式的字符串，但 FSA 无法告诉您总和是多少。但是，您不能为此添加括号，否则 FSA 不再足够。换句话说，识别字符串和计算结果之间存在差异，FSA 通常被认为是前者。