我试图创建一个可以识别带有字母 {a,b,c} 的字符串的 DFA，其中 a 和 c 出现偶数次，而 b 出现奇数次。
我想知道这可能只能用图灵机或无上下文语言等其他方法来表达。
您可能会觉得考虑解决方案很有趣。
问问题
110 次
2 回答
1
我将要构建这样一台机器的方法如下。做八种状态。每个状态代表一个可能的 3 元组组合。开始状态是表示所有三个为偶数的组合的状态。如果 a 是输入中的第一个字符，那么您将进入一个表示奇数个 a 和偶数个 b 和 c 的状态。接受状态是 a 和 c 为偶数，b 为奇数。
于 2012-12-16T04:48:48.380 回答
0
这是可能的，使用 DFA 只需为奇数个 a、b 和 c 的组合中的每个组合提供一个状态。因此，如果您处于具有偶数 # 个 a、奇数 # 个 b 和偶数 # 个 c 的状态，那么您可以接受。您还可以为任何其他情况定义简单的转换。所以天真地这可以用 8 个状态来完成。
于 2012-12-16T04:43:41.117 回答