Clarification regarding concatenation and union in regular expressions.

$\begingroup$

I'm just having a little trouble understanding the precedence relationship between the concatenation and union operators in regular expressions.

Specifically (for my problem), given the regular expression:

$(aa^*+ba^*)^* . (bbb+ab^*)+(ab)^*$

Would it be correct to treat the order of operation as follows:

$((aa^*+ba^*)^* . (bbb+ab^*))+(ab)^*$

Thank you in advance.

$\endgroup$ 3

1 Answer

$\begingroup$

The order of operations, for regular operations is star (highest precedence), product, union. Thus you are right, $(aa^*+ba^*)^* (bbb+ab^*)+(ab)^*$ is equivalent to $((aa^*+ba^*)^* (bbb+ab^*))+(ab)^*$. Note however that you should avoid the dot in your expressions, otherwise you should also write $a \cdot a^*$ for instance.

By the way, this is the same precedence order than for the three operations exponent, product, sum for numbers.

$\endgroup$

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

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