基于语言的 DFA {0,1}
DFA over language {0,1}
我正在努力满足以下要求（作业）
Construct both regular expression and deterministic automatons that
accept the following languages over {0,1}.
(a) Strings that do not contain 00.
(b) Strings that contain at least three symbols.
(c) Strings where each 0 is directly followed by 1.
(d) Strings that both start and end with 11.
(e) Strings having an odd number of 0:s and an odd number of 1:s.
到目前为止我已经完成了以下操作，但感觉不对，有人对我可以做得更好有什么建议吗？我对此很陌生，甚至不知道我所做的是否符合要求。
我发现制作正则表达式比 DFA 更难，所以我建议先制作 DFA，然后再制作正则表达式。
(a) 我们可以制作一个 DFA 来检测子字符串 00 并转换到死状态。
q s q'
-- -- --
q0 0 q1 q0 is the initial state
q0 1 q0 q0 and q1 are accepting
q1 0 q2 q2 is a dead state
q1 1 q0
q2 0 q2
q2 1 q2
为了获得正则表达式，我们迭代地为每个状态找到一个正则表达式，用于指向该状态的字符串。然后，我们将所有正则表达式的并集用于接受状态。
iteration 1
q0: e + (q0)1 + (q1)1
q1: (q0)0
q2: (q1)0 + (q2)0 + (q2)1
iteration 2
q0: e + (q0)1 + (q0)01
q1: (q0)0
q2: (q0)00 + (q2)0 + (q2)1
iteration 3
q0: e+(1+01)*
q1: (e+(1+01)*)0
q2: (e+(1+01)*)00(0+1)*
因为q0和q1是接受状态，所以正则表达式是
e+(1+01)*+(e+(1+01)*)0
= (1+01)*+(1+01)*0 // e + r* = r*
= (1+01)*e+(1+01)*0 // r = re
= (1+01)(e+0) // distributive law of concatenation
(b) 这里的 DFA 是：
q s s'
-- -- --
q0 0 q1
q0 1 q1 q0 is the initial state
q1 0 q2 q3 is the accepting state
q1 1 q2
q2 0 q3
q2 1 q3
q3 0 q3
q3 1 q3
同样的练习：
iteration 1
q0: e
q1: (q0)0 + (q0)1
q2: (q1)0 + (q1)1
q3: (q2)0 + (q2)1
iterations 2-3 (combined)
q0: e
q1: e0 + e1
q2: (0+1)0 + (0+1)1
q3: (q2)0 + (q2)1 + (q3)0 + (q3)1
iteration 4
q0: e
q1: e0 + e1
q2: (0+1)0 + (0+1)1
q3: ((0+1)0 + (0+1)1)(0+1)(0+1)*
因为q4是唯一的接受状态，答案就是
((0+1)0 + (0+1)1)(0+1)(0+1)*
= (00+10+01+11)(0+1)(0+1)*
(c) 这与 (a) 非常相似，只是我们丢弃了以 0 结尾的字符串。也就是说，q1 不接受。因此，DFA 与 (a) 中的相同，q1 不接受，因此正则表达式只是 e+(1+01)* = (1+01)*.
(d) 一个 DFA：
q s q'
-- -- --
q0 0 q1
q0 1 q2 q0 is the initial state
q1 0 q1 q3 is the accepting state
q1 1 q1 q1 is the dead state
q2 0 q1 q0,q1,q2 ensure the string starts with 11
q2 1 q3 q3,q4,q5 ensure the string stops with 11
q3 0 q4
q3 1 q3
q4 0 q4
q4 1 q5
q5 0 q4
q5 1 q3
我们当然可以完成与上面相同的练习，但这里的正则表达式实际上很容易制作：11+111+11(0+1)*11.
(e) 一个 DFA：
q s q'
-- -- --
q0 0 q1
q0 1 q2 q0 is the initial state
q1 0 q0 q3 is the accepting state
q1 1 q3 q0: #0 and #1 are even
q2 0 q3 q1: #0 is odd, #1 is even
q2 1 q0 q2: #0 is even, #1 is odd
q3 0 q2 q3: #0 is odd, #1 is odd
q3 1 q1
这里的正则表达式比较难，留作练习。您可以像前面的示例一样进行迭代；请记住规则是：
qx: r + (qx)s ---> qx: (r)(s*)
然后一次只消去一个符号，直到你有一个没有状态占位符的 (q3) 的正则表达式。祝你好运。
我正在努力满足以下要求（作业）
Construct both regular expression and deterministic automatons that accept the following languages over {0,1}.
(a) Strings that do not contain 00.
(b) Strings that contain at least three symbols.
(c) Strings where each 0 is directly followed by 1.
(d) Strings that both start and end with 11.
(e) Strings having an odd number of 0:s and an odd number of 1:s.
到目前为止我已经完成了以下操作，但感觉不对，有人对我可以做得更好有什么建议吗？我对此很陌生，甚至不知道我所做的是否符合要求。
我发现制作正则表达式比 DFA 更难，所以我建议先制作 DFA，然后再制作正则表达式。
(a) 我们可以制作一个 DFA 来检测子字符串 00 并转换到死状态。
q s q'
-- -- --
q0 0 q1 q0 is the initial state
q0 1 q0 q0 and q1 are accepting
q1 0 q2 q2 is a dead state
q1 1 q0
q2 0 q2
q2 1 q2
为了获得正则表达式，我们迭代地为每个状态找到一个正则表达式，用于指向该状态的字符串。然后，我们将所有正则表达式的并集用于接受状态。
iteration 1
q0: e + (q0)1 + (q1)1
q1: (q0)0
q2: (q1)0 + (q2)0 + (q2)1
iteration 2
q0: e + (q0)1 + (q0)01
q1: (q0)0
q2: (q0)00 + (q2)0 + (q2)1
iteration 3
q0: e+(1+01)*
q1: (e+(1+01)*)0
q2: (e+(1+01)*)00(0+1)*
因为q0和q1是接受状态，所以正则表达式是
e+(1+01)*+(e+(1+01)*)0
= (1+01)*+(1+01)*0 // e + r* = r*
= (1+01)*e+(1+01)*0 // r = re
= (1+01)(e+0) // distributive law of concatenation
(b) 这里的 DFA 是：
q s s'
-- -- --
q0 0 q1
q0 1 q1 q0 is the initial state
q1 0 q2 q3 is the accepting state
q1 1 q2
q2 0 q3
q2 1 q3
q3 0 q3
q3 1 q3
同样的练习：
iteration 1
q0: e
q1: (q0)0 + (q0)1
q2: (q1)0 + (q1)1
q3: (q2)0 + (q2)1
iterations 2-3 (combined)
q0: e
q1: e0 + e1
q2: (0+1)0 + (0+1)1
q3: (q2)0 + (q2)1 + (q3)0 + (q3)1
iteration 4
q0: e
q1: e0 + e1
q2: (0+1)0 + (0+1)1
q3: ((0+1)0 + (0+1)1)(0+1)(0+1)*
因为q4是唯一的接受状态，答案就是
((0+1)0 + (0+1)1)(0+1)(0+1)*
= (00+10+01+11)(0+1)(0+1)*
(c) 这与 (a) 非常相似，只是我们丢弃了以 0 结尾的字符串。也就是说，q1 不接受。因此，DFA 与 (a) 中的相同，q1 不接受，因此正则表达式只是 e+(1+01)* = (1+01)*.
(d) 一个 DFA：
q s q'
-- -- --
q0 0 q1
q0 1 q2 q0 is the initial state
q1 0 q1 q3 is the accepting state
q1 1 q1 q1 is the dead state
q2 0 q1 q0,q1,q2 ensure the string starts with 11
q2 1 q3 q3,q4,q5 ensure the string stops with 11
q3 0 q4
q3 1 q3
q4 0 q4
q4 1 q5
q5 0 q4
q5 1 q3
我们当然可以完成与上面相同的练习，但这里的正则表达式实际上很容易制作：11+111+11(0+1)*11.
(e) 一个 DFA：
q s q'
-- -- --
q0 0 q1
q0 1 q2 q0 is the initial state
q1 0 q0 q3 is the accepting state
q1 1 q3 q0: #0 and #1 are even
q2 0 q3 q1: #0 is odd, #1 is even
q2 1 q0 q2: #0 is even, #1 is odd
q3 0 q2 q3: #0 is odd, #1 is odd
q3 1 q1
这里的正则表达式比较难，留作练习。您可以像前面的示例一样进行迭代；请记住规则是：
qx: r + (qx)s ---> qx: (r)(s*)
然后一次只消去一个符号，直到你有一个没有状态占位符的 (q3) 的正则表达式。祝你好运。