We can prove that two regular expressions are equivalent by showing that their minimum-state DFA's are the same up to renaming of states. Show in this way that the following regular expressions:...

We can prove that two regular expressions are equivalent by showing that their minimum-state DFA's are the same up to renaming of states. Show in this way that the following regular expressions: (a|b)*, (a*|b*)*, and ((e|a)b*)* are all equivalent. Note: You may have constructed the DFA's for these expressions in response to Exercise 3.7.3.

Exercise 3.7.3

Convert the following regular expressions to deterministic finite automata, using algorithms 3.23 and 3.20:

a) (a|b)*.

b) (a*|b*)*.


c) ((e|a)b*)*.


d) (a|b)*abb(a|b)*.