我正在学习一门计算课程，该课程还教授正则表达式。有一个很难回答的问题。
找到接受最多包含两对连续 0 的单词的语言的正则表达式。字母表由 0 和 1 组成。
首先，我制作了该语言的 NFA，但无法将其转换为 GNFA（后来被转换为正则表达式）。我怎样才能找到这个正则表达式？是否将其转换为 GNFA？
问问题
2767 次
3 回答
3
（由于这是一个家庭作业问题，我假设您只需要足够的帮助来开始，而不是一个完整的解决方案？）
您的里程可能会有所不同，但我真的不建议尝试将 NFA 转换为正则表达式。两者在理论上是等价的，并且可以通过算法转换为另一个，但在我看来，这不是构造任何一个的最直观的方式。
相反，一种方法是从列举各种可能性开始：
根本没有成对的连续零；也就是说，每个零，除了字符串的末尾，必须跟一个一。
1因此，字符串由and的混合序列组成01，可选地后跟0：(1|01)*(0|ε)正好一对连续的零，在字符串的末尾。这与上一个非常相似：
(1|01)*00恰好是一对连续的零，而不是在字符串的末尾——因此，后面必然跟着一个 1。这也与第一个非常相似：
(1|01)*001(1|01)*(0|ε)
要继续这种方法，您将扩展上述内容以支持两对连续零；最后，您会将所有这些合并到一个正则表达式中。
于 2012-03-17T18:17:09.537 回答
0
(0+1)*00(0+1)*00(0+1)* + (0+1)*000(0+1)*
于 2015-07-08T09:22:23.167 回答
-1
最多包含两对连续的 0
(1|01)*(00|ε)(1|10)*(00|ε)(1|10)*
于 2013-03-09T21:38:35.810 回答