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

Question

我在正则表达式中进行了以下任务,我无法理解这些问题.

L1 = {0 ⁿ 1 ^m | n≥3∧m是奇数}

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

Answer 1

答案是什么？

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

000+1(11)*¹

那这是做什么的呢？

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

我怎么样的？

关键是了解正则表达式语法.我碰巧有相当多的经验,但这个网站帮助我验证.

一旦了解了正则表达式的基本构建块,就需要将问题分解为可以表示的问题.

例如,正则表达式允许我们为匹配({x,y}语法)指定较低的AND上限,但不允许仅指定下限({x}将完全匹配x时间).所以我知道我必须要么使用+或*指定为零,因为这些是允许匹配的无限数量的唯一符.我也知道将这些修饰符应用于一个组是没有意义的; 我们必须至少有3个零的限制并不意味着我们必须有三个的倍数,例如,所以(000)+出来了.我不得不将修饰符仅应用于一个字符,这意味着我必须首先匹配几个文字.000保证匹配正好三个0s,0*(最终表达式0000*)完全符合我的要求,然后我将其浓缩为等效的000+.

对于第二个条件,我不得不考虑奇数是多少.根据定义,奇数可以表示为2*k + 1,其中k是整数.所以我必须匹配一个1(因此是文字1)和一些子串11.这导致了我的团队,然后是*.在略有不同的问题上,您可以编写1(11)+匹配任何奇数个,并且至少3个.

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