# DFA or NFA Construction

I have to draw a DFA or NFA for a language that has two symbols lets say {0,1}. The condition is "such that exactly one of the two symbols 0 or 1 appears at least three times." I understood this as if 0 appears three times or more than 1 can be there for 0,1 or 2 times and if 1 appears for 3 times or more DFA fails and goes to dead state. The same will happen for the case if 1 appears 3 times or more and if 0 can be there for 0,1 or 2 times and if 0 appears for 3 times or more DFA fails and goes to dead state. I have been trying to create a DFA for this but failing everytime on condition like "01010". I am not sure if it is possible to create a DFA or NFA for this. I guess this is solvable by PDA only. Need help in making sure that I am thinking in right direction.

• There is certainly a DFA for this problem. When processing a letter, you only need to know how many of each you have already seen, capped at 3. So there are only 4*4=16 possibilities. – rici Oct 6 '17 at 13:25

Let note them $Q_{i,j}$ where $i \in \{0,1,2,3,4\}$ is the number of 0 and $j \in \{0,1,2,3,4\}$ is the number of 1; each up to a max of 4 $\implies$ only 25 states.
$\delta(Q_{i,j}, 0) = Q_{i+1,j}$ if $i<4$
$\delta(Q_{4,j}, 0) = Q_{4,j}$
$\delta(Q_{i,j}, 1) =Q_{i,j+1}$ if $j<4$
$\delta(Q_{i,4}, 1) =Q_{i,4}$
Then the starting state is $Q_{0,0}$ and the accepting states are all $Q_{i,j}$ with $i=0 \oplus j = 1$ (where $\oplus$ is the xor operator).