0
$\begingroup$

I'm looking at a proof that says that: If $M_1=(Q_1, \Sigma , q_1, A_1, \delta)$ and $M_2=(Q_2, \Sigma , q_2, A_2, \delta)$ are two finite automata(FA) then $M=M_1 \cup M_2$ is also an FA. We define $M=(Q, \Sigma , q, A, \delta)$ where $Q=Q_1 \times Q_2$, $q_0=(q_1,q_2)$ and $\delta((p,q),\sigma)=(\delta(p,\sigma),\delta(q,\sigma))$.

I'm just having one problem. We have to prove that $\delta^*((p,q),x)=(\delta^*(p,x),\delta^*(q,x))$. (x is a string in $\Sigma^*$) We do it by induction. I've already proven the base case, and I'm now trying to prove it holds for $x'=x\sigma$. This is what I've gotten so far:

$\delta^*((p,q),x')=\delta(\delta^*((p,q),x),\sigma)=\delta(\delta^*(p,x),\delta^*(q,x)),\sigma)$

I don't really know how to proceed from here. Can someone help?

$\endgroup$
  • 2
    $\begingroup$ Can you give a little bit more context, e.g. a natural language explanation of statement and proof idea? This is to check what you (think you) understood, which is usually indicative of the problem you have. $\endgroup$ – Raphael Jun 25 '14 at 13:05
  • 1
    $\begingroup$ You are using the symbol for union, the title says intersection! $\endgroup$ – saadtaame Jun 25 '14 at 13:51
  • $\begingroup$ @saadtaame. Quite right, but except for consistency between title and body, the same construction works for both union and intersection, as long as one suitably defines the accept states in the cartesian product automaton. $\endgroup$ – Rick Decker Jun 25 '14 at 14:33
  • 1
    $\begingroup$ You did not define $A$, though it is crucial. Your automata are 4-tuples, and union of tuples is not exactly a classical concept. You should use another symbol preferably, or at least explain your use of $\cup$. The base case of the induction can be done trivially with $x=\epsilon$. You should call your transition function $\delta_i$ for the automaton $M_i$ to avoid confusion. Then you would see that all you need is applying to the right-hand side of your induction formula the definition of the transition function $\delta$ for automaton $M$. Systematic notations can make your life much easier. $\endgroup$ – babou Jun 25 '14 at 15:06
  • $\begingroup$ @babou. I agree. A more felicitous statement would have been to define a FA $M$ such that $L(M)=L(M_1)\cup L(M_2)$. $\endgroup$ – Rick Decker Jun 25 '14 at 19:43
2
$\begingroup$

A possible source of your confusion is that the transition functions of $M_1$, $M_2$ and $M$ are different functions, yet you call all of them $\delta$. If instead you use $\delta_1$ resp. $\delta_2$ for the transition function of $M_1$ resp. $M_2$, the definition of $\delta$ changes to $\delta((p,q),\sigma)=(\delta_1(p,\sigma),\delta_2(q,\sigma))$. You should be able to add the subscripts in the appropriate positions of your partial proof yourself.

Now, after noting that $\delta_1^*(p,x)\in Q_1$ and $\delta_2^*(q,x)\in Q_2$, the proof can be completed by a straightforward application of the definitions of $\delta$ and $\delta_i^*$.

$\endgroup$

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.