我在正则表达式中有以下问题,但我无法解决这类问题。
L1 = { 0n1m | n≥3 ∧ m is odd }
当字母表是 {0,1} 时,我如何为这类问题编写正则表达式。
最佳答案
答案是什么?
您的示例的正则表达式是:
000+1(11)*
1
那么这是做什么的呢?
- 前两个字符
00
是原义的零。这对下一点很重要 - 后两个字符,
0+
,意思是“至少有一个零,没有上限”。这前四个字符满足第一个条件,即我们至少有三个零。 - 下一个字符
1
是一个字面值。因为我们需要有奇数个,所以这是我们允许的最小数量 - 最后一个字符
(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 个。
1 我的一位同事向我指出,+
运算符在技术上不是正则表达式正式定义的一部分。如果这是一个学术问题而不是编程问题,您可能会发现 0000*
版本更有帮助。在这种情况下,最终字符串将是 0000*1(11)*
关于regex - 如何将语言集表示法转换为正则表达式?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/26286147/