In Sipser's Introduction to the Theory of Computation, the provided proof for the union operation being closed for regular languages has a step for the transition function that I find a bit lacking.

Assuming that $M_1=(Q_1, \Sigma, \delta_1, q_1, F_1)$ and $M_2=(Q_2, \Sigma, \delta_2, q_2, F_2)$ are two different FSMs for languages $L_1$ and $L_2$. With $M=(Q, \Sigma, \delta, q_0, F)$ being the FSM for $L = L_1 \cup L_2$ (the regular languages for the FSMs). The step for the constructed transition function, $\delta$, states that for each $(r_1,r_2) \in Q$ and each $a \in \Sigma$, let $\delta((r_1,r_2),a)=(\delta_1(r_1,a),\delta_2(r_2,a))$. This is working with the assumption that the input alphabet, $\Sigma$, is the same for $M_1$ and $M_2$.

I am confused on how $\delta((r_1,r_2),a)=(\delta_1(r_1,a),\delta_2(r_2,a))$ behaves for a combined alphabet $\Sigma = \Sigma_1 \cup \Sigma_2$, specifically if $a \in \Sigma_1$ and $a \notin \Sigma_2$? What would the output of $\delta_2(r_2,a)$ be and how would this transition work in the FSMs $M_2$ and $M$?


1 Answer 1


In my copy of the book, third edition, this is Theorem 1.25. From its proof, I quote:

The theorem remains true if they have different alphabets, $\Sigma_1$ and $\Sigma_2$. We would then modify the proof to let $\Sigma = \Sigma_1\cup \Sigma_2$.

What is suggested here is that in advance we assume the two alphabets to be equal, i.e., before we start the product construction. So we have to transform the original automaton $M_1$ with alphabet $\Sigma_1$ into an equivalent automaton $M_1'$ with alphabet $\Sigma_1\cup \Sigma_2$ accepting the same language. As you observe automata here are deterministic, i.e., have a transition function $\delta:Q\times \Sigma\to Q$.

The easiest way for the construction of $M_1'$ is extending the transition function for letters outside $\Sigma_1$. Any such letter should lead to not accepted computations. This can be done by adding a new garbage (or failure state) where all letters from $\Sigma_2\setminus \Sigma_1$ are mapped to.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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