1
$\begingroup$

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!

$\endgroup$
1
$\begingroup$

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)^*)^* $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.