Automata theory and regular expessions prove that (A ∪ B)* = A*(BA*)*.
To prove that (A ∪ B)* = A*(BA*)*, we need to show that every string in (A ∪ B)* is also in A*(BA*)* and vice versa.
First, let's start with (A ∪ B)* ⊆ A*(BA*)*, meaning any string in (A ∪ B)* belongs to A*(BA*)*.
To do this, consider an arbitrary string w in (A ∪ B)*. Since w is in (A ∪ B)*, it is a concatenation of zero or more strings from A and/or B. We can split w into its constituent parts, where each part is either from A or from B.
Now, we will construct a corresponding string x in A*(BA*)*. Let's denote the parts of w from A as a1, a2, ..., ak and the parts from B as b1, b2, ..., bm.
We can then construct x as follows:
x = a1(a2a3...ak(b1a2a3...ak)*bm)*
Here's an explanation of how x is constructed:
- The first part a1 is included as it is.
- The subsequent parts from A (a2, a3, ..., ak) are concatenated together.
- After the parts from A, we start with the first part from B (b1) followed by the concatenated parts from A (a2, a3, ..., ak) enclosed in parentheses and repeated zero or more times (a2a3...ak)*.
- Finally, we append the remaining parts from B (b2, b3, ..., bm).
Now, let's see why x is equivalent to w:
- a1 corresponds to the first part of w, which is from A since it was denoted as a part of w from A.
- The subsequent concatenation of a2, a3, ..., ak corresponds to the other parts of w from A since they were denoted as parts of w from A.
- The section (b1a2a3...ak)* corresponds to the parts of w from B (if any). The parts from B in w are sandwiched between parts from A in x.
- The final section bm corresponds to the remaining parts of w from B since they were denoted as parts of w from B.
Therefore, we have shown that any string in (A ∪ B)* can be constructed in the form A*(BA*)*, which proves (A ∪ B)* ⊆ A*(BA*)*.
Next, we need to show the reverse containment, which is A*(BA*)* ⊆ (A ∪ B)*.
To prove this, consider an arbitrary string y in A*(BA*)*. Since y is in A*(BA*)*, it can be constructed by concatenating zero or more strings from A, followed by a string from B, and then zero or more strings from A again.
Let's construct a corresponding string z in (A ∪ B)*:
z = a1b1a2b2a3b3...akbk
Here's an explanation of how z is constructed:
- The first part a1 corresponds to a string from A in y.
- The first part b1 corresponds to a string from B in y.
- The subsequent parts a2, a3, ..., ak correspond to the remaining strings from A in y.
- The subsequent parts b2, b3, ..., bk correspond to the remaining strings from B in y.
Therefore, we have shown that any string in A*(BA*)* can be constructed in the form (A ∪ B)*, which proves A*(BA*)* ⊆ (A ∪ B)*.
Since we have proved both (A ∪ B)* ⊆ A*(BA*)* and A*(BA*)* ⊆ (A ∪ B)*, we can conclude that (A ∪ B)* = A*(BA*)*.
Note: The proof presented here is a constructive proof, showcasing how to construct equivalent strings in both sets. It can be helpful to clearly understand the reasoning behind the equality of these two expressions.