string 具有偶数个 a 和奇数个 b 的字符串的正则表达式

Regular expression for strings with even number of a's and odd no of b's

提问by Abu Mathew

Im having a problem in solving the problem:- Its an assignment, i solved it, but it seems to be too long and vague, Can anyboby help me please......

我在解决问题时遇到了问题：- 这是一个作业，我解决了它，但它似乎太长且含糊不清，请任何人帮助我......

Regular expression for the strings with even number of a's and odd number of b's where the character set={a,b}.

具有偶数个 a 和奇数个 b 的字符串的正则表达式，其中字符集={a,b}。

回答by paxdiablo

One way to do this is to pass it through tworegular expressions making sure they both match (assuming you want to use regular expressions at all, see below for an alternative):

一种方法是通过两个正则表达式传递它以确保它们都匹配（假设您根本想使用正则表达式，请参见下面的替代方案）：

^b*(ab*ab*)*$
^a*ba*(ba*ba*)*$

Anything else (and, in fact, even that) is most likely just an attempt to be clever, one that's generally a massive failure.

其他任何事情（事实上，甚至那个）很可能只是一种聪明的尝试，通常是一个巨大的失败。

The first regular expression ensures there are an even number of awith banywhere in the mix (before, after and in between).

第一个正则表达式确保在混合中的任何地方（之前、之后和之间）都有偶数个awith b。

The second is similar but ensures that there's an oddnumber of bby virtue of the starting a*ba*.

第二个是类似的，但可以确保有一个奇数编号的b借助于起动a*ba*。

---

---

A far betterway to do it is to ignore regular expressions altogether and simply run through the string as follows:

一个更好的方法是完全忽略正则表达式并简单地运行字符串，如下所示：

def isValid(s):
    set evenA to true
    set oddB to false
    for c as each character in s:
        if c is 'a':
            set evenA to not evenA
        else if c is 'b':
            set oddB to  not oddB
        else:
            return false
    return evenA and oddB

Though regular expressions are a wonderful tool, they're not suited for everything and they become far less useful as their readability and maintainability degrades.

尽管正则表达式是一个很棒的工具，但它们并不适合所有情况，而且随着可读性和可维护性的降低，它们变得越来越没用。

---

---

For what it's worth, a single-regex answer is:

就其价值而言，单一正则表达式的答案是：

(aa|bb|(ab|ba)(aa|bb)*(ba|ab))*(b|(ab|ba)(bb|aa)*a)

but, if I caught anyone on my team actually using a monstrosity like that, they'd be sent back to do it again.

但是，如果我发现我的团队中有人真的使用了这样的怪物，他们就会被送回去再做一次。

This comes from a paper by one Greg Bacon. See herefor the actual inner workings.

这来自格雷格·培根 (Greg Bacon) 的一篇论文。请参阅此处了解实际的内部工作原理。

回答by Veenu

Even-Even = (aa+bb+(ab+ba)(aa+bb)*(ab+ba))*

(Even-Even has even number of Aas and b's both)

（Even-Even 有偶数个 Aas 和 b 两个）

Even a's and odd b's = Even-Even b Even-Even

偶数 a 和奇数 b = 偶数 b 偶数

This hsould work

这应该有效

回答by Pooja Consul

This regular expression takes all strings with even number of a's and even number of b's

此正则表达式采用所有具有偶数个 a 和偶数个 b 的字符串

r1=((ab+ba)(aa+bb)*(ab+ba)+(aa+bb))*

Now to get regular expression for even a's and odd b's

现在获得偶数 a 和奇数 b 的正则表达式

r2=(b+a(aa+bb)*(ab+ba))((ab+ba)(aa+bb)*(ab+ba)+(aa+bb))*

回答by Abhinav Rastogi

For even number of a's and b's , we have regex:

对于偶数 a 和 b ，我们有正则表达式：

E = { (ab + ba) (aa+bb)* (ab+ba) }*

For even number of a's and odd number of b's , all we need to do is to add an extra bin the above expression E.

对于偶数a和奇数b，我们需要做的就是b在上面的表达式中添加一个额外的东西E。

The required regex will be:

所需的正则表达式将是：

E = { ((ab + ba) (aa+bb)* (ab+ba))* b ((ab + ba) (aa+bb)* (ab+ba))* }

回答by vandanak

1. (bb)*a(aa)*ab(bb)*
2. ab(bb)* a(aa)*
3. b(aa)*(bb)*.
   .
   .
   .
   .
   .

1. (bb)*a(aa)*ab(bb)*
2. ab(bb)* a(aa)*
3. b(aa)*(bb)*.
   .
   .
   .
   .
   .

there can be many such regular expressions. Do you have any other condition like "starting with a" or something of the kind (other than odd 'b' and even 'a') ?

可以有很多这样的正则表达式。您是否有任何其他条件，例如“以 a 开头”或类似的条件（除了奇数 'b' 甚至是 'a'）？

回答by Fabian Pijcke

I would do as follows:

我会这样做：

• regex evenmatches the symbol a, then a sequence of b's, then the symbol aagain, then another sequence of b's, such that there is an even number of b's:

• regex甚至匹配符号a，然后是b的序列，然后是符号a，然后是另一个b序列，这样b的数量是偶数：

even-> (a(bb)* a(bb)* | ab(bb)* ab(bb)*)

偶数-> ( a( bb)* a( bb)* | a b( bb)* a b( bb)*)

• regex odddoes the same with an odd total number of b's:

• 正则表达式奇确实具有的总数是奇数同一b的：

odd-> (ab(bb)* a(bb)* | a(bb)* ab(bb)*)

奇数-> ( a b( bb)* a( bb)* | a( bb)* a b( bb)*)

A string of even number of a's and odd number of b's either:

一串偶数a和奇数b：

• starts with an odd number of b's, and is followed by an even number of oddpatterns amongst evenpatterns;
• or starts with an even number of b's, and is followed by an odd number of oddpatterns amongst evenpatterns.

• 以奇数个b开始，然后是偶数模式中的偶数个奇数模式；
• 或具有偶数个的开始b“s和后跟奇数的奇数之中图案甚至图案。

Note that evenhas no incidence on the evenness/oddness of the a/b's in the string.

请注意，even与字符串中a/ b的偶数/奇数无关。

regex -> (

正则表达式 -> (

b(bb)* even*(oddeven*odd)* even*

b( bb)*偶*(奇偶*奇)*偶*

|

|

(bb)* even*oddeven*(oddeven*odd)* even*

( bb)*偶*奇偶*(奇偶*奇)*偶*

)

)

Of course one can replace every occurence of evenand oddin the final regex to get a single regex.

当然，可以替换最终正则表达式中出现的偶数和奇数，以获得单个正则表达式。

It is easy to see that a string satisfying this regex will indeed have an even number of a's (as symbol aoccurs only in evenand oddsubregexes, and these each use exactly two a's) and an odd number of b's (first case : 1 b+ even number of b's + even number of odd; second case : even number of b's + odd number of odd).

很容易看出，满足此正则表达式的字符串确实将具有偶数个a's（因为符号a仅出现在偶数和奇数子正则表达式中，并且它们每个都恰好使用两个a's）和奇数个b' s（第一种情况：1 b+ b的偶数+奇数的偶数；第二种情况：b的偶数 + 奇数的奇数）。

A string with an even number of a's and an odd number of b's will satisfy this regex as it starts with zero or more b's, then is followed by [one a, zero or more b's, one more aand zero or more b's], zero or more times.

具有偶数个a和奇数个b的字符串将满足此正则表达式，因为它以零个或多个b开头，然后是 [一个a，零个或多个b，再一个a和零个或多个b的]，零次或多次。

回答by blazs

A high-level advice: construct a deterministic finite automaton for the language---very easy, encode parity of the number of as and bs in the states, with q0encoding even nr. of as and even nr. of bs, and transition accordingly---, and then convert the DFA into a regular expression (either by using well-known algorithms for this or "from scratch").

高级建议：为语言构建一个确定性有限自动机——非常简单，编码状态中as 和bs数量的奇偶校验，q0甚至编码 nr。的as乃至NR。的bs和过渡相应---，然后（通过使用公知的算法为这个或“从头开始”要么）转换成DFA正则表达式。

The idea here is to exploit the well-understood equivalence between the DFA (an algorithmic description of regular languages) and the regular expressions (an algebraic description of regular languages).

这里的想法是利用 DFA（正则语言的算法描述）和正则表达式（正则语言的代数描述）之间众所周知的等价性。

回答by Ricky

The structured way to do it is to make one transition diagram and build the regular expression from it. The regex in this case will be

结构化的方法是制作一个转换图并从中构建正则表达式。在这种情况下，正则表达式将是

(a((b(aa)*b)*a+b(aa)*ab)+b((a(bb)*a)*b+a(bb)*ba))b(a(bb)*a)*

It looks complicated but it covers all possible cases that may arise.

它看起来很复杂，但它涵盖了所有可能出现的情况。

回答by rashedcs

The regular expression are given below :

正则表达式如下：

    (aa|bb)*((ab|ba)(aa|bb)*(ab|ba)(aa|bb)*b)*

回答by Nishant Chaturvedi

the answer is (aa+ab+ba+bb)* b (aa+ab+ba+bb)*

答案是 (aa+ab+ba+bb)* b (aa+ab+ba+bb)*