我该如何检查一台特定的粉碎机是否可以生成特定的输出？

Question

如果我有一台粉碎机，并且我有一个很大的字符串，我该如何检查粉碎机是否可以生成该字符串？

我想过把mealy机器转换成正则表达式，但我不清楚如何做到这一点。

谢谢。

Answer 1

我会从最后开始。反转所有方向（是的，这意味着一个门现在可以接收一个值并输出两个），并以相反的顺序使用该字符串作为输入。无论何时你到达某个门或黑匣子元素，你都有它的输出;找出可能导致该输出的所有可能输入，并继续非确定性地向后退出。
如果在字符串的末尾达到某个输入（或一组输入），那么（或那些）输入就是生成给定字符串的输入。否则，该字符串不能被该机器生成。

另一种方法（有时更简单，有时不会）会尝试查看机器生成的所有字符串是什么，或尝试查找所有这些字符串必须满足的属性，并且给定的字符串的作用不是（例如，如果你不知道机器生成的字符串是什么，但是你知道它们都以“A”开始，并且给定的字符串没有）。