2
$\begingroup$

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)'

enter image description here

enter image description here

enter image description here

enter image description here

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 ?

$\endgroup$
  • $\begingroup$ "These are pairs of FA's. Set theory formula in here is" -- I don't know what you are trying to say. Seems to be in the category "it's not even wrong". $\endgroup$ – Raphael Feb 22 '14 at 9:47
  • $\begingroup$ Also, why did you remove large parts of your question? The remainder was useless. Are you trying to cover your tracks after cheating? $\endgroup$ – Raphael Feb 22 '14 at 9:49
  • $\begingroup$ @Raphael I manage to understand what was intended. The question is a total mess. And the answer concerns only a detail and thus does not clear the mess. There is no way that (L1' + L2)' + (L2' + L2)' can be understood as a symetrical difference which is supposed to be the union of 2 intersections, or the sum of two products. What are the voters thinking of ??? True though that the answerer understood the question ... strange. $\endgroup$ – babou Feb 23 '14 at 20:39
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ thanks for your input...I don't understand the math syntax very much, I will look over you answer again until I completely understand. $\endgroup$ – Dana Feb 21 '14 at 20:42
  • $\begingroup$ I am not sure I understand. Once you have built the product, what do you do with it to answer the question. cc@Dana $\endgroup$ – babou Feb 22 '14 at 17:21
  • $\begingroup$ The question is a total gibberish that you somehow managed to outguess. This answer can be satisfactory only if you explain clearly what the question intended to do (your first sentence does it in a way), and repeat correctly the erroneous formula given for symmetrical difference. Make it something useful for other readers. I am still surprised by this answer, as it seems a hard way to do things. Taking the complement is not necessarily cheap. It is more a theoretical construct than a practical way to do things, I would think. Given these automata, there might be an easier way. $\endgroup$ – babou Feb 23 '14 at 20:54
  • $\begingroup$ I acknowledge there is room for improvement and if I find the time I will update it. But the formula for the symmetric difference given in the question is correct (it equals $(L_1 \cap L_2^\complement) \cup (L_1^\complement \cap L_2) = (L_1 \setminus L_2) \cup (L_2 \setminus L_1)$. Furthermore, for $L$ derived from regular languages $L_1, L_2$ through $L = \{ w \mid w \in L_1 \bowtie w \in L_2\}$ you can construct an automaton using product construction and applying $\bowtie$ to the acceptance predicate. I forgot to mention that the resulting DFA has to accept $\Sigma^*$, which it does. $\endgroup$ – misberner Feb 24 '14 at 13:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.