0

如果我有一台mealy机器,并且我有一个大字符串,我如何检查mealy机器是否可以生成该字符串?

我考虑过将mealy机器转换为正则表达式,但我也不清楚如何做到这一点。

谢谢你。

4

1 回答 1

0

我会从最后开始。反转所有方向(是的,这意味着门现在可以接收一个值并输出两个),并以相反的顺序使用字符串作为输入。每当您到达某个门或黑匣子元素时,您就会得到它的输出;找出所有可能导致该输出的输入,并继续不确定地倒退。
如果在字符串的末尾到达某个输入(或一组输入),则该(或那些)输入是产生给定字符串的输入。否则,该字符串不能由该机器生成。

另一种方法(有时更简单,有时不是)是尝试查看机器生成的所有字符串是什么,或者尝试找到所有这些字符串必须满足而给定字符串不满足的某个属性(例如,如果您并不确切知道机器生成了哪些字符串 aer,但您知道它们都以“A”开头,而给定的字符串不是)。

于 2011-09-19T22:07:18.640 回答