There are some threads that discuss it but I haven't came across an inductive one yet. All of them involve creating a finite automaton which I would like to avoid (as per my professors requests).


1 Answer 1


You can use regular expressions to easily solve this:

$$(L_1\cup L_2)^r=L_1^r\cup L_2^r$$ $$(L_1\cap L_2)^r=L_1^r\cap L_2^r$$ $$(L_1L_2)^r=L_2^rL_1^r$$ $$(L^*)^r=(L^r)^*$$

You can use these equalities when proving by induction over the number of operators in the regular expression.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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