Regular expression for strings that cointains a and an even number of b's

1.5k views Asked by At

How to define a regular expression to feature the following language?

L = {w ∈ {a, b}* | w has an even number of b's}

I tried to create the related automaton:

enter image description here

and from that i tried to apply the algorithm to obtain regular espression from DFA and i get this formula: a*ba*b.

Could this be the right answer?

2

There are 2 answers

9
Mazdak On BEST ANSWER

You are close but you need a a* in the end of your pattern.You also need the anchors ^ and $ for specifying the start and end of your string.Then you can put all of your regex within a capture group and use * to match any even number if b, and an a* for zero number of b:

 ^((a*ba*ba*)*|a*)$

Note: | is a logical OR and makes your regex engine match (a*ba*ba*)* or a*.

Regular expression visualization

Debuggex Demo

You can also make it more elegant but as you are not familiar very much with regex first i suggested the preceding pattern.

For example the following will works :

^(((a*b){2})*)a*$
0
smartmouse On

Here is the best solution because i follow the algorithm for conversion from DFA to regular expression (done by pen):

(a*|ba*b)*

You can test it here and you can learn about this algorithm watching this video.