如果我必须使用状态图绘制确定性有限自动机,以便接受一种语言,例如 {λ ε {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 回答