[Solved]: showing that the pair of Finite Automata are equivalent

Problem Detail: 

Here I am trying to show that the pair of Finite Automata are equivalent. I have tried something but I am not sure if I am in the right direction. This is what I have.

These are pairs of FA's. Set theory formula in here is (L1' + L2)' + (L2' + L2)'

Conclusion:

Both machines (FA1'+FA2)' and (FA2+FA1)' has no final states. (FA1'+FA2)' to have a final state, the machine (FA1'+FA2)' must have no final state. The exact same thing half of the formula. Clearly, if we added these machines together we would get a machine with nine state and no final state. Because there is no final state, it accepts no words and two languages L1 and L2 ar equivalent.

So the two regular expressions defame the same language and equivalent.

Am I in the right direction ?

Asked By : Dana

Answered By : misberner

Your approach works. You are effectively showing that the symmetric difference $L(FA_1) \Delta L(FA_2)$ is empty, hence $L(FA_1) = L(FA_2)$.

A more direct, automaton-level approach would be to build the following product automaton $A = (Q, \Sigma, \delta, q_0, F)$:

• $Q = Q_1 \times Q_2$
• $\delta((q_1, q_2), a) = (\delta(q_1, a), \delta(q_2, a)) \ \forall (q_1, q_2) \in Q, a \in \Sigma$
• $q_0 = (q_{0,1}, q_{0,2})$
• $F = \{(q_1, q_2) \in Q \mid q_1 \in F_1 \Leftrightarrow q_2 \in F_2\}$

Intuitively, you keep in mind the current state in both $FA_1$ and $FA_2$. Initially, the current states are the respective initial states $q_{0,1}$ and $q_{0,2}$. Then, for each input symbol $a$, you move to the respective successor in each automaton, and note the successor state (the combination of the two successor states as a pair). Of course you only draw the state for each combination only once. You can proceed either breadth-first (considering all input symbols for one product state before moving on to a newly introduced state) or depth-first (always continue with the newly introduced state and backtracking if all product successor already existed).

Note that this way you might not have to construct the full product set $Q_1 \times Q_2$, as you automatically prune unreachable states (you don't ever introduce them). However, the product automaton in your example will have no more than 6 states anyway, so it is rather small.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/21897