Skip to main content
3 of 6
corrected the title
Awaisome
  • 35
  • 1
  • 6

regex - difference between (a+b)*b AND (aa*b)*

FA
$r_1=\Lambda+(a+b)^*b$
$r_2=(b+aa^*b)^*$
$r_3=b+\\\$+aa^*b+(b+\\\$+aa^*b)(b+aa^*b)*(b+\\\$+aa^*b)$

For this FA, which i think of as accepting "$\Lambda$ or anything ending in $b$", i came up with $r_1$, then i used FSM2Regex which gave me $r_3$ which i simplified into $r_2$ using regex simplifier.
now $r_2$ seems better than $r_1$. should i go with it? if so, what is lacking in $r_1$? i can't see the difference b/w $(a+b)^*b$ from $r_1$ AND $(aa^*b)^*$ from $r_2$. is one the subset of other? are they overlapping or disjoint?
Inputting any of the three RE's back into FSM2Regex gives RIDICULOUSLY complex TG's esp cuz for reason that is beyond me, it also draws $ (null string) transitions. even $r_3$ doesn't give back the FA i used to generate it. so question is : are $r_1$ and $r_2$ different? how? what should i go with?

Awaisome
  • 35
  • 1
  • 6