如果我必须使用状态图绘制确定性有限自动机，以便接受一种语言，例如 {λ ε {a,b}*：单词 λ 包含偶数个 a 和奇数个 b}，如何我知道我有多少个州？
问问题
412 次
1 回答
1
4个状态就够了。您需要同时满足两个条件：偶数个 a 和奇数个 b。彼此无关，每个条件都可以是真或假。
如果我们用 1表示真，用 0 表示假，我们会得到 4种不同的不同可能性：两者都是假的，其中一个（但不是另一个）为真，或两者都为真。因此，我们得到一个真值表：
even a | odd b
---------------
0 0
0 1
1 0
1 1
让我们用 表示第一行q[0, 0]，第二行q[0, 1]以此类推。现在我们必须指定每个状态的转换，以及识别我们的初始状态。
无论我们处于何种状态，都有两种可能的输入：a或b。因此，对于每个状态，我们必须指定两个转换。
现在，我们的初始状态是我们在使用任何输入之前所处的状态。由于 0 是偶数，我们得到我们的初始状态是q[1, 0]。我们的接受状态是两个条件都满足时，即q[1, 1]。
最后，我们有我们的状态转换，
q[0, 1]是我们的初始状态
q[1, 0] reads b -> q[1, 1]
q[1, 0] reads a -> q[0, 0]
q[1, 1]是我们的接受状态
q[1, 1] reads b -> q[1, 0]
q[1, 1] reads a -> q[0, 1]
q[0, 1]只有当我们至少阅读过一个a
q[0, 1] reads b -> q[0, 0]
q[0, 1] reads a -> q[1, 1]
q[0, 0]只有当我们至少阅读过一个a
q[0, 0] reads b -> q[0, 1]
q[0, 0] reads a -> q[1, 0]
于 2016-07-16T16:10:39.777 回答