Question

Prove that $\mathit{E}{\mathit{Q}}_{\mathbf{D}\mathbf{F}\mathbf{A}}$ is decidable by testing the two DFAs on all strings up to a certain size. Calculate a size that works.

Short answer

The string length must be less than or equal to n.m, where$A\left(w^n\right)\ne B\left(w^m\right).$

Step-by-step solution

Explain decidability

A problem is decidable if all the instances of that problem are accepted. A Turing machine is used to decide a problem.

Calculate a size that works

Construct a Turing machine that takes the input w, with the size of n.m for$A\left(w\right)\ne B\left(w\right).$

By contradiction, the first string provides a different output of the DFAs A and B which is $w\text{'}$. The length l of $\left|w\text{'}\right|$is greater than n.m.

The sequence of the states of A and B are $a_0,a_1,a_2,\dots a_l$and $b_0,b_1,b_2,\dots b_l,$which describe the transition $w\text{'}.$

The value of l is greater than n.m, if the above sequences are provided as input then $a_i=a_j,b_i=b_j,i<j$are also present.

Therefore, the string w has the length less than equal to n.m such that $A\left(w^n\right)\ne B\left(w^m\right)$.

Therefore, the string length must be less than or equal to n.m , where $A\left(w^n\right)\ne B\left(w^m\right)$.