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 回答