0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – rici Oct 6 '17 at 13:25
1
$\begingroup$

You only have a limited number of states to worry about:

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.

Then the transition is
$\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).

$\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.