This DFA fulfills:
Define a function diff:{0,1}∗→Zdiff:{0,1}∗→Z, for w∈{0,1}∗w∈{0,1}∗, diff(w)=(diff(w)=(# of 1's in w)−(w)−(# of 0's in ww).
Thus, diff(ϵ)=0diff(ϵ)=0; diff(0)=−1diff(0)=−1; diff(1)=1diff(1)=1.
Let L={w∈{0,1}∗∣diff(w)=3m for some m∈Z}L={w∈{0,1}∗∣𝑑𝑖𝑓𝑓(w)=3m for some m∈Z}.
but I have been stuck when I go to proving correctness of DFA.
-
the first option:
∀w∈{0,1}∗∀w∈{0,1}∗: a) if δ(q0,w)=q1δ(q0,w)=q1, then w∈Lw∈L and bin(w)=3∗a+1 bin(w)=3∗a+0, for any a∈Z+a∈Z+.
-
the second option:
∀w∈{0,1}∗∀w∈{0,1}∗: a) if δ(q0,w)=q1δ(q0,w)=q1, then w∈L and w=0, for any a∈Z+a∈Z+.
What would be the correct option?
