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).
2
-
$\begingroup$ Your professors will be very happy to learn that the recursive solution for the regex reverse is found in several answers. By templatetypedef: How to show that a "reversed" regular language is regular, by Yuval: Closure under reversal of regular languages: Proof using Automata and also How to prove a language is regular? and then by Vor: How to prove closure property of regular languages using regular expressions? $\endgroup$– Hendrik JanFeb 26, 2022 at 20:40
-
$\begingroup$ What do you mean by "reversal"? $\endgroup$– xskxzrMar 1, 2022 at 1:47
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
answered Feb 26, 2022 at 11:02