I have a problem in solving the following exercise and I'd appreciate any help.
我在解决以下练习时遇到问题,我会感激任何帮助。
Let Σ = {a,b}. I need to give a regular expression for all strings containing an odd number of a.
设Σ= {a,b}。我需要为包含奇数a的所有字符串提供正则表达式。
Thank you for your time
感谢您的时间
2 个解决方案
#1
6
b*(ab*ab*)*ab*
the main part of it is (ab*ab*)*, which enumerate all possibilities of even number of as. then at last, an extra a has to exist to make it odd.
它的主要部分是(ab * ab *)*,它列举偶数个as的所有可能性。然后最后,必须存在额外的a才能使它变得奇怪。
notice that this regular expression is equivalent to:
注意这个正则表达式相当于:
b*a(b*ab*a)*b*
these two constructs are in the form defined by pumping lemma:
这两个结构是由泵引理定义的形式:
http://en.wikipedia.org/wiki/Pumping_lemma
UPDATE:
@MahanteshMAmbi presented his concern of the regular expression matching the case aaabaaa. In fact, it doesn't. If we run grep, we shall see clearly what is matched.
@MahanteshMAmbi表达了他对正则表达式匹配案例aaabaaa的关注。事实上,它没有。如果我们运行grep,我们将清楚地看到匹配的内容。
$ echo aaabaaa | grep -P -o 'b*(ab*ab*)*ab*'
aaabaa
a
-o option of grep will print each matching instance every line. In this case, as we can see, the regular expression is being matched twice. One matches 5 as, one matches 1 a. The seeming error in my comment below is caused by an improper test case, rather than the error in the regular expression.
-o选项grep将每行打印每个匹配的实例。在这种情况下,正如我们所看到的,正则表达式被匹配两次。一个匹配5,一个匹配1a。下面我的评论中的看似错误是由不正确的测试用例引起的,而不是正则表达式中的错误引起的。
If we want to make it rigorous to use in real life, it's probably better to use anchors in the expression to force a complete string match:
如果我们想要在现实生活中使用它是严格的,那么在表达式中使用锚点来强制完整的字符串匹配可能更好:
^b*(ab*ab*)*ab*$
therefore:
$ echo aaabaaa | grep -P -q '^b*(ab*ab*)*ab*$'
$ echo $?
1
#2
0
^[^a]*a(?=[^a]*(?:a[^a]*a)*[^a]*$).*$
This will find only odd number of a's for any generic string.See demo.
这将找到任何通用字符串的奇数个。参见演示。
#1
6
b*(ab*ab*)*ab*
the main part of it is (ab*ab*)*, which enumerate all possibilities of even number of as. then at last, an extra a has to exist to make it odd.
它的主要部分是(ab * ab *)*,它列举偶数个as的所有可能性。然后最后,必须存在额外的a才能使它变得奇怪。
notice that this regular expression is equivalent to:
注意这个正则表达式相当于:
b*a(b*ab*a)*b*
these two constructs are in the form defined by pumping lemma:
这两个结构是由泵引理定义的形式:
http://en.wikipedia.org/wiki/Pumping_lemma
UPDATE:
@MahanteshMAmbi presented his concern of the regular expression matching the case aaabaaa. In fact, it doesn't. If we run grep, we shall see clearly what is matched.
@MahanteshMAmbi表达了他对正则表达式匹配案例aaabaaa的关注。事实上,它没有。如果我们运行grep,我们将清楚地看到匹配的内容。
$ echo aaabaaa | grep -P -o 'b*(ab*ab*)*ab*'
aaabaa
a
-o option of grep will print each matching instance every line. In this case, as we can see, the regular expression is being matched twice. One matches 5 as, one matches 1 a. The seeming error in my comment below is caused by an improper test case, rather than the error in the regular expression.
-o选项grep将每行打印每个匹配的实例。在这种情况下,正如我们所看到的,正则表达式被匹配两次。一个匹配5,一个匹配1a。下面我的评论中的看似错误是由不正确的测试用例引起的,而不是正则表达式中的错误引起的。
If we want to make it rigorous to use in real life, it's probably better to use anchors in the expression to force a complete string match:
如果我们想要在现实生活中使用它是严格的,那么在表达式中使用锚点来强制完整的字符串匹配可能更好:
^b*(ab*ab*)*ab*$
therefore:
$ echo aaabaaa | grep -P -q '^b*(ab*ab*)*ab*$'
$ echo $?
1
#2
0
^[^a]*a(?=[^a]*(?:a[^a]*a)*[^a]*$).*$
This will find only odd number of a's for any generic string.See demo.
这将找到任何通用字符串的奇数个。参见演示。