Final answer:
Yes, it is possible to decide if two regular expressions describe the same language by comparing their equivalent DFAs for equivalence. However, this process does not run in polynomial time due to potential exponential size of the resulting DFAs.
Step-by-step explanation:
The question of whether two regular expressions describe the same language is known as the equivalence problem for regular expressions. It is indeed possible to decide if two regular expressions denote the same language. The procedure typically involves converting both expressions into their equivalent deterministic finite automata (DFA) and then comparing these DFAs for equivalence. Two DFAs are equivalent if they recognize exactly the same set of strings.
To compare whether two DFAs are equivalent, one approach is to construct a DFA for the symmetric difference of the languages of the two DFAs and then check if the resultant DFA accepts any string. If it does not, the original DFAs are equivalent. However, the conversion of a regular expression to a DFA can result in an exponential blow-up in the size of the DFA, potentially leading to an exponential time complexity for the equivalence checking process.
Whether the equivalence of regular expressions can be decided in polynomial time is a more complex question. The current consensus in theoretical computer science is that equivalence checking for regular expressions cannot be done in polynomial time due to the potential exponential size of the equivalent DFAs. Therefore, this problem is generally not considered to be solvable in polynomial time.