PLease help me understand this DFA, why does int(101)=5? Why is the DFA drawn th

Question

PLease help me understand this DFA, why does int(101)=5? Why is the DFA drawn the way it is??

Thanks!

Let w {0,1}^+, and int(w) be the decimal number represented by w. For instance, int(101) = 5. We wish to design a DFA A, such that L(A) = {w {0,1}^+ : int(w^R) is divisible by 5}. Note the w^R. The R means that we want to accept those bitstrings that represent integers whose reverse is divisible by 5. Answer: First we design a DFA to accept L^R(A), the bitstrings w where int(w) is divisible by 5. Now we can reverse this DFA to accept L(A) as:

Explanation / Answer

for example consider a bit string 101 whose decimal value is equal to 5 . The question is accept a string whose revers e should be divisible by 5 .now consider the above binary string w=101 is divisible by 5 as well as w^r(reverse of w)=101 which is also divisible by 5 so this bit string is acceptable consider another bitstring 110 whose decimal value is equal to 10 which is divisible by 5 but the reverse of the string will be w^r=011 whose decimal value is 3 which is not divisible by 5 so this string is not acceptable.this is the meaning of the question

to construt this type of DFA first we need to consider the normal case and then by reversing the directions of arrows we will get the reverse case so first what he did is he constructed a DFA for the strings which are divisible by 5

consider the example w=101 i.e., 5 which should be accepted

let us see step by step from first diagram

q0 on 1 ----->q2

q2 on 0 ------>q1

q1 on 1 ------> q0(which is final state) i.e., the string is accepted

now consider the reverse of the bit string w^r=101 i.e., 5 which is divisible by 5

from figure 2

q0 on 1 ----->q2

q2 on 0 ------>q1

q1 on 1 ------->q0 (final state)

i.e., the string 101is accepted

if you consider the case of 110 it is accepted in fig1 and not accepted in fig2 as the reverse of 110=011 which is not divisible by 5

try with more strings to get more clarity

hope you understood .Thank You:)

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.