2

我刚开始学习形式语言和自动机理论，最近学习了正则表达式，所以我不知道任何复杂的符号，所以请坚持使用基本符号。

问题是：为以下语言编写一个正则表达式，{0, 1}它是一组所有奇数长度的字符串，其中正好包含两个0s。

我已经完成了第一部分（奇怪的部分），它应该是：

(0+1)[(0+1)(0+1)]*（与（或）+相同，|我相信，我们将其学习为+）

但是，当我想到正好有两个0s 时，它真的搞砸了。我只能看到我只能使用*with ，1因为 # of 0s 仅限于2. 但如果我这样做(11)*了，我就无法得到0s 在1s 中的排列。（例如不能得到10101）(11)*。

我知道的：

  1. 只有1s 可以使用*
  2. 在正则表达式中，只会0使用两个 s
  3. 制作奇数长度的方法是将奇数长度添加到偶数长度（偶数长度需要在其中设置空字符串）
  4. 奇数长度不应该使用*，因为 2 奇数 = 偶数，所以只有偶数长度可以使用*。

对于可能的提示或答案，请仅使用0, 1, +/ |, *, (, )。其他一些表达我将无法理解。

4

1 回答 1

2

常规语言{0, 1}是一组所有奇数长度的字符串，其中正好包含两个0.

这种语言是什么意思？

注意语言字符串可以由两个0 和任意数量组成，1这样字符串的总长度是奇数。没有其他限制。1 并且0 以任何顺序和任何模式出现。

我们知道even+ odd= odd。所以 in string 至少由三个长度和奇数组成，1因为0in string 的数量是两个。

所以正则表达式应该是这样的： ，其中 A、B、C 是子字符串，并且 A、B、C 中的总数 是奇数，因此在表达式中不能都是(nul)。A 0 B 0 C 11^

现在因为 A、B、C 中的总数1 = 奇数，所以它可以是：every(1)two even and one odd或 (2) all three are odd。

注意：奇数长度的字符串不能为空。

正则表达式： 

1(11)*01(11)*01(11)* + 1(11)*0(11)*0(11)* + (11)*01(11)*0(11)* + (11)*0(11)*01(11)*
// all odd             A odd, B C even       B odd, A C even     A B even, C odd
于 2013-09-22T18:15:27.017 回答