DFA This DFA fulfills:

Define a function $diff: \{0,1\}^*\to\Bbb Z$, for $w \in\{0,1\}^*$, $diff(w)=($# of 1's in $w)- ($# of 0's in $w$).

Thus, $diff(\epsilon)=0$; $diff(0)=−1$; $diff(1)=1$.

Let $L = \{w\in \{0,1\}^* \mid 𝑑𝑖𝑓𝑓(w) = 3m\text{ for some }m\in\Bbb Z \}$.

but I have been stuck when I go to proving correctness of DFA.

  • the first option:

    $\forall w \in \{0,1\}^*$: a) if $\delta(q_0,w)= q_1$, then $w\in L$ and $bin(w) = 3 * a + 0$, for any $a \in \Bbb Z^+$.

  • the second option:

    $\forall w \in \{0,1\}^*$: a) if $\delta (q_0,w)= q_1$, then $w\in L$ and $w =1$, for any $a\in \Bbb Z^+$.

What would be the correct option?

  • $\begingroup$ Your DFA is counting modulo 6 rather than modulo 3. $\endgroup$ – Yuval Filmus Apr 2 '19 at 14:39
  • $\begingroup$ What change should I make to count module 3? $\endgroup$ – Ives Rodriguez Apr 2 '19 at 14:59
  • $\begingroup$ You should have only three states. $\endgroup$ – Yuval Filmus Apr 2 '19 at 15:00
  • $\begingroup$ I don't think it's counting modulo 6. It's just not minimal. Back to the original question, I'd say that both your claims are fairly useless when it comes to proving correctness of the DFA. Try something that relates an input word $w$ to where it takes you from any state $q_i$ in terms of your $\mathit{diff}$ function. $\endgroup$ – Kai Apr 3 '19 at 10:40
  • $\begingroup$ @Kai The DFA is counting modulo 6. Which state you are in is the number of 0s minus the number of 1s modulo 6. $\endgroup$ – Yuval Filmus Apr 3 '19 at 11:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.