Some regular expression conversions from the examples: b | ba | bbb*a | a | ab | aaa*b ba | bbb*a ==> b (a | bb*a) ==> b ((ε | bb*) a) ==> b (b* a) ==> bb*a ab | aaa*b ==> a (b | aa*b) ==> a ((ε | aa*) b) ==> a (a* b) ==> aa*b b | bb*a | a | aa*b bb*a | a | aa*b | b bb*a | a ==> (bb* | ε) a ==> (ε | bb*) a ==> (b*) a ==> b*a aa*b | b ==> (aa* | ε) b ==> (ε | aa*) b ==> (a*) b ==> a*b