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 that you have read and understand our privacy policy and code of conduct.

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