Is A(BA)* = (AB)*A
A and B are both languages over the same alphabet
I think this is incorrect but I can’t come up with any examples that might show it.
if a belongs to A ,b belongs to B,
BA = ba
(BA)* = {ba, baba, bababa…}
AB = ab
(AB)* = {ab, abab, ababa…}
A(BA)* = {a, aba, ababa,…}
(AB)*A = {a, aba, ababa, …}
2
You can prove that both define the same language by converting both regular expressions to minimal DFAs, and compare those. The process of creating a minimal DFA for a regular expression can be broken down into these steps:
-
Construct an NFA for the language using Thompson’s construction
-
Convert that NFA to a DFA using powerset construction
-
Apply a DFA minimisation algorithm to that DFA.
A(BA)*
1. Construct NFA
Using Thompson’s construction we arrive at this NFA:
Note that where the transitions are labeled A or B, this means that they group all composite transitions from start to accept state in the DFAs for language A or B respectively.
2. Construct DFA
With power construction, we get this DFA from it (I omit the reject sink):
3. Minimize
Using the “non-distinguishable states” step for minimizing DFAs, we find that states {1} and {4} are equivalent (both are non-accept states, and they have the same set of outgoing transitions), and states {2,3,6} and {3,5,6} are equivalent (they are both accepting and have the same set of outgoing transitions). Both pairs can thus be merged, and so we get:
(AB)*A
1. Construct NFA
Using Thompson’s construction we arrive at this NFA:
2. Construct DFA
With power construction, we get this DFA from it (I omit the reject sink):
3. Minimize
Using the “non-distinguishable states” step for minimizing DFAs, we find that states {1,2,5} and {2,4,5} are equivalent (both are non-accept states, and they have the same set of outgoing transitions). That pair can thus be merged, and so we get:
Comparison
Apart from the different names that were given to the states of the final two minimized DFAs, they are the same. And so we can conclude that both regular expressions define the same language.
There is also a regex to min-DFA tool by GitHib user CyberZHG, which arrives at the same minimized DFA for both regular expressions.
1