regex - regular expression evaluation in string matching -


i reading regular expression in algorithms robert sedgwick book.

here regular expression mention below

a* | (a*ba*ba*)* 

here author mentioned matches are: aaa, bbaabb, , babaaa. not match above regular expression aba bbb babbaaa.

my question how bbaabb matching , same way how babaaa matching. kindly explain.

in general looking how evaluate | , * operators in regular expressions. in below example how can b alone in set if have a+ since says must have atleast 1 a.

(a+b)* = (λ, a, b, aa, ab, ba, bb, aaa, ...) 

there 1 difference between * , +. character after put * can have no repetition. in + case, can have minimum 1 repetition. in a* | (a*ba*ba*)*, bbaabb valid following reasons , according (a*ba*ba*)* pattern

  1. no a @ start a*
  2. 1 b ba* , no a
  3. 1 b ba* , 2 a
  4. * @ end of (a*ba*ba*)*shows pattern can repeat. second repetition bb valid

these points bbaabb valid.


Comments