我真的需要一些帮助，我制作了大约 100 个构建 DFA 的示例，但我一直坚持这个。任何帮助都感激不尽。
所以我有一些随机 bool 函数，例如: f(a,b,c,d) = (a∨c)∧((a∧b)∨(c ↔ d)) 我应该制作一个 DFA 接受所有为真的字符串 {3,7, 8,11,12,13,14,15(二进制))其他所有内容都应该被拒绝。所以基本上我需要一个 DFA 将这些整数转换为二进制形式并接受它们，拒绝剩下的其他整数。我怎么做到的？我花了几个小时试图询问各州。在这种情况下你如何制作转换表？
再次感谢您对我的帮助! :)
最佳答案
如果我正确理解了这个问题，那么这个问题“相对容易”，因为输入的大小是固定的，这意味着接受的语言也是有限的。我会给出一个构造的草图，这会导致相对较多的状态，但不会使用复杂的想法。
用真值表检查公式。有 4 个变量需要评估，这意味着有 2^4 = 16 个可能的输入。
将这些输入排列在由从根(DFA 的初始状态)到 16 叶的 16 条路径组成的决策树中。当且仅当通向叶子的路径对应于真值表中评估为"is"的输入时，叶子才是最终状态。
请注意，有限语言总是有可能被 DFA 识别 - 构造一个 NDFA，它接受该语言中的每个单词，并将其转换为 DFA(细节上可能很复杂，但这样的自动机通过 this 构造保证存在)。
关于function - 设计检查 bool 公式是真还是假的 DFA，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/45918423/