regex - 如何将语言集表示法转换为正则表达式？

Question

我在正则表达式中有以下问题，但我无法解决这类问题。

L1 = { 0ⁿ1^m | n≥3 ∧ m is odd }

当字母表是 {0,1} 时，我如何为这类问题编写正则表达式。

Answer 1

答案是什么？

您的示例的正则表达式是:

000+1(11)*¹

那么这是做什么的呢？

1. 前两个字符 00 是原义的零。这对下一点很重要
2. 后两个字符，0+，意思是“至少有一个零，没有上限”。这前四个字符满足第一个条件，即我们至少有三个零。
3. 下一个字符 1 是一个字面值。因为我们需要有奇数个，所以这是我们允许的最小数量
4. 最后一个字符 (11) 表示两个文字的逻辑分组，结尾的 * 表示匹配此分组零个或多个次。因为我们总是至少有一个 1，所以我们总是匹配一个奇数。所以我们完成了。

我是怎么得到的？

关键是了解正则表达式语法。我碰巧在这方面有相当多的经验，但是this网站帮我验证。

了解正则表达式的基本构建 block 后，您需要将问题分解为您可以表示的内容。

例如，正则表达式允许我们指定匹配的下限和上限({x,y} 语法)，但不允许仅指定下限( {x} 将精确匹配 x 次)。所以我知道我必须使用 + 或 * 来指定零，因为它们是唯一允许无限数量匹配的说明符。我也知道将这些修饰符应用于一个组是没有意义的；我们必须至少有 3 个零的限制并不意味着我们必须有三的倍数，例如，所以 (000)+ 被淘汰了。我必须将修饰符仅应用于一个字符，这意味着我必须先匹配几个文字。 000 保证正好匹配三个 0，而 0*(最终表达式 0000*)正是我想要的，然后我将其压缩为等效的 000+。

对于第二个条件，我不得不思考什么是奇数。根据定义，奇数可以用2*k + 1表示，其中k是一个整数。所以我必须匹配一个 1(因此是文字 1)和一些子字符串 11。这让我进入了小组，然后是 *。在一个稍微不同的问题上，您可以编写 1(11)+ 来匹配任何奇数个，至少 3 个。

---

¹ 我的一位同事向我指出，+ 运算符在技术上不是正则表达式正式定义的一部分。如果这是一个学术问题而不是编程问题，您可能会发现 0000* 版本更有帮助。在这种情况下，最终字符串将是 0000*1(11)*