我们能不能计算出在以下约束条件下可以设计的 dfa 的总数（即最大数量）：|Q|=2{No. 状态数为 2},|Ɛ|=2{No. 字母} 和 |F|=1{No. 最终状态} ?
问问题
1006 次
1 回答
1
首先，我猜测“字母数量”实际上是指字母表中符号的数量。我还没有听说过具有多个字母的有限自动机。
接下来，我所拥有的有限自动机的定义是： 有限自动机 M 是五元组 M = (S,I,δ,s0,F) 其中： S 是有限集（状态） I 是有限字母表（输入符号) δ: S × I → S (下一个状态函数) s0 ∈ S (起始状态) F ⊆ S (接受状态)。
所以你的定义映射到我的 Q -> SƐ -> I and F -> F
现在，哪个状态是起始状态会导致不同的自动机，所以这是一个重要的因素，不能忽略。如果您有 2 个状态，那么从这两个状态中选择不同的最终状态会导致两个不同的自动机。现在假设每个状态的字母表中的每个符号都必须有一个转换函数，然后只检查一个状态开始，对于每个状态，两个符号（称为 a 和 b）中的每一个都必须有一个转换函数. 每个符号的转换函数的值可以是两种可能状态之一。因此，对于单个状态，可能存在 2 x 2 = 4 个转换函数。由于有两个状态，第二个状态还有另外 4 个可能的转换函数。考虑不同初始/最终状态的可能性，
于 2016-03-28T21:15:40.940 回答