Peter Linz Edition 4 Exercise 2.1 Question 7-c,d,e,f (Page No. 47)

Question

100. L= {w: $n_{a}(w) mod \ 3 >1$}

500. L= {w: $n_{a}(w) mod \ 3 >n_{b}(w)mod \ 3$}

5. L= { w: $(n_{a}(w) - n_{b}(w))\mod \ 3>0$

6. L= {w: $(n_{a}(w) + 2n_{b}(w))\mod \ 3<2$}

Please verify above three dfa for the given languages. I think all three are correct, just doing it for surety and help me to find out the correct dfa for f)

Comments

e is not right as it is accepting abb but it should not be accepted as 1-2=-1< 0

---

(-1 mod 3) is 2 >0 which is greater than zero.

---

aabbb on question d

---

for part f :

there are 3 states, p,q and r, where p is initial state and p,q are final states.

p on a, q

p on b, r

q on a, r

q on b, p

r on a, p

r on b, q

---

(-1 mod 3) is 2

From whom u learnt this?

---

Thank you sir. But how to approach this kind of question by generating certain strings or any other logic especially e and f ?

---

by experience you will get @kushagra

moreover no need to call me as sir, you can call me by name

---

find −b modN , just keep adding N to −b until the number is between 0 and N

As an example, N=13, b=−27 Add 13 to -27, you get -14, again you get -1, and again you get 12.

So, −27 mod13 =12

 

One more way:

Take $−100\ mod\ 8= 4$. This is because $8\times−13=−104$ The remainder is 4.

.