In both parts, provide an analysis of the time complexity of your algorithm.

a. Show that${\mathbf{EQ}}_{\mathbf{DFA}}\in \mathbf{P}$.

b. Say that a language$\mathbf{A}\mathbf{is}\mathbf{star}-\mathbf{closed}\mathbf{if}\mathbf{A}=\mathbf{A}*$. Give a polynomial time algorithm

to test whether a $\mathbf{DFA}$recognizes a star-closed language. (Note that $\mathbf{EQNFA}$is not

known to be in $\mathit{P}$.)

$F_{DFA}$might establish that is a decidable language by building a Turing machine $\left(TM-1\right)$that would take tape input if it marked any accept state, but would reject it otherwise. To put it another way, a $DFA$on a truing machine will be simulated.

If both $DFAs$accept the same language, we can create a Turing machine that accepts a string if it belongs in one of the machines, but not both at the same time. We might achieve the end state by running $BFSorDFS$from the beginning. The time complexity is $O\left(\left|V\right|+\left|E\right|\right),$where$V$represents the number of states in a $DFAandE$represents the number of edges. We can observe which transitions were utilised once we discover the end state from the start state, and we can execute such a string on our Turing machine. This would take O(string-length), a polynomial time.

The resolution in time complexity using$BFSorDFS$$BFSorDFS$.