I need to write a regular expression for the following set of strings on Σ = {a, b, c} in which the number of b’s is even, and contains abcba as a substring.
So far, the even number of b's can be constructed using like this:
(aUb(aUc)*bUc)* or (cUa)*b(cUa)*b(cUa)*
to add the substring abcba, do I just attach it to the end of the regular expression and then repeat it or is there a better way?
Any help is appreciated!
Any string containing $abcba$ is of the form $xabcbay$, where $x,y$ are strings. This string contains an even number of $b$'s iff $xy$ contains an even number of $b$'s iff either $x,y$ both contain an even number of $b$'s, or both contain an odd number of $b$'s. This leads to the following regular expression: $$ (a+c)^*(b(a+c)^*b(a+c)^*)^*abcba(a+c)^*(b(a+c)^*b(a+c)^*)^* + \\ (a+c)^*b(a+c)^*(b(a+c)^*b(a+c)^*)^*abcba(a+c)^*b(a+c)^*(b(a+c)^*b(a+c)^*)^* $$
