patternMinor
Problems while trying to prove that $(r|s)^* = (r^*.s^*)^*$
Viewed 0 times
whiletryingprovethatproblems
Problem
I came across the following equality of regular expressions $$(r|s)^ = (r^.s^)^\,,$$ where $r$ and $s$ are two regular expressions and $.$ denotes concatenation, but I don't know how could I prove it.
My try:
I call $L(r)$ the language defined by the regular expression $r$. And I want to use the fact that two regular expressions $r$ and $s$ are equal iff $L(r) = L(s)$.
The LHS can be writen as follows: $$ L((r|s)^{*}) = \bigcup_{i=0}^{+\infty} L(r|s)^{i} = \bigcup_{i=0}^{+\infty} (L(r)^{i} \cup L(s)^{i})\,. $$
The RHS can be writen as follows:
$$ L((r^{}.s^{})^{}) = \bigcup_{i=0}^{+\infty} L((r^{}.s^{*}))^{i}\,.$$
But I got stuck at this point and I don't know how to proceed.
My try:
I call $L(r)$ the language defined by the regular expression $r$. And I want to use the fact that two regular expressions $r$ and $s$ are equal iff $L(r) = L(s)$.
The LHS can be writen as follows: $$ L((r|s)^{*}) = \bigcup_{i=0}^{+\infty} L(r|s)^{i} = \bigcup_{i=0}^{+\infty} (L(r)^{i} \cup L(s)^{i})\,. $$
The RHS can be writen as follows:
$$ L((r^{}.s^{})^{}) = \bigcup_{i=0}^{+\infty} L((r^{}.s^{*}))^{i}\,.$$
But I got stuck at this point and I don't know how to proceed.
Solution
In one direction,
$$
L((r^s^)^) \subseteq L(((r|s)^(r|s)^)^) = L(((r|s)^)^) = L((r|s)^*).
$$
In the other direction, $L(r) \subseteq L(r^s^)$ and $L(s) \subseteq L(r^s^)$ imply that $L(r|s) \subseteq L(r^s^)$, and so
$$
L((r|s)^) \subseteq L((r^s^)^).
$$
$$
L((r^s^)^) \subseteq L(((r|s)^(r|s)^)^) = L(((r|s)^)^) = L((r|s)^*).
$$
In the other direction, $L(r) \subseteq L(r^s^)$ and $L(s) \subseteq L(r^s^)$ imply that $L(r|s) \subseteq L(r^s^)$, and so
$$
L((r|s)^) \subseteq L((r^s^)^).
$$
Context
StackExchange Computer Science Q#72325, answer score: 6
Revisions (0)
No revisions yet.