6

m+n 为偶数的语言 0 m 1 n的正则表达式是什么？

4

2 回答 2

14

如果您的意思是字符串000...111...长度为偶数的字符串，您可以使用^(00)*(01)?(11)*$

于 2010-03-09T15:31:07.760 回答
1

好的，因此您需要将奇数和偶数的情况考虑为零。这需要两种状态，一种用于偶零，一种用于奇零。然后对于奇零情况，您需要有 1 个，然后是偶数个。对于偶数情况，您只需要偶数个。

写 DFA 很容易，但我不知道如何在这里绘制，所以我将冒险猜测正则表达式：

(0 (00)* 1 (11)*) \/ (00)*(11)*
于 2010-03-09T16:02:08.007 回答