Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
Cute problem. I hadn't seen it before, and I've been doing this for decades. –  Rick Decker Feb 6 '13 at 0:51
add comment

2 Answers

up vote 5 down vote accepted

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

share|improve this answer
add comment

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.

share|improve this answer
    
+1, this was my first thought too. It generalizes to a direct proof that the class of regular languages is closed under arbitrary Boolean functions (without needing to know that some particular set of opearators is complete). –  Henning Makholm Feb 6 '13 at 2:09
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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