How can I prove the majority of three languages is also regular if the three languages are regular?

Question

This is a question I've been stuck on recently:

Let $A$, $B$, and $C$ be three languages over the same alphabet. Define $\mathrm{maj}(A,B,C)$ to be the collection of all strings $w$ that occur in at least two of the three languages (that is, $w$ is in the majority of the languages). Prove that if $A$, $B$, and $C$ are regular, then so is $\mathrm{maj}(A,B,C)$.

I've been thinking of ways to do this problem. I know that there are two theorems, one which states that if two languages are regular, then the intersection of those languages are also regular. Also if two languages are regular, then the union of them is also regular.

So I've been thinking, that if I do the union of all three languages, each contain the string $w$, would that prove that the $\mathrm{maj}(A,B,C)$ is also regular? I can't seem to figure out any other ways to prove it? Can anyone tell me if I am going on the right track with the theorem or if there is more to it?

Answer 1

You can use $${\rm maj}(A,B,C)=(A\cap B)\cup(A\cap C)\cup(B\cap C).$$

Answer 2

You can also combine DFAs for $A,B$, and $C$ to make one that accepts $\operatorname{maj}(A,B,C)$. The basic idea is that if the state sets of the original DFAs are $Q_A,Q_B$, and $Q_C$, the state set of the new one will be $Q_A\times Q_B\times Q_C$. For each $\alpha$ in the input alphabet you’ll have a transition

$$\langle q_A,q_B,q_C\rangle\overset{\alpha}\longrightarrow\langle q_A\,',q_B\,',q_C\,'\rangle$$

iff the original automata have transitions $q_A\overset{\alpha}\longrightarrow q_A\,'$, $q_B\overset{\alpha}\longrightarrow q_B\,'$, and $q_C\overset{\alpha}\longrightarrow q_C\,'$. A state $\langle q_A,q_B,q_C\rangle$ will be an acceptor state iff at least two of $q_A,q_B$, and $q_C$ are acceptor states in their respective automata.