GB TOC Q13

Question

Which of the following is not regular?

(A). {/n>=0 and input alphabet is {a,b}}       

(B).  where i+j+k>100 & k>50

(C).  where i+j+k>100 & j+k>50                  

(D). None of the above

Comments

Both B and C ??

---

answer given is D :(

---

This means all are regular or none are regular??

Answer 1

1. a⁴ⁿ/n>=0 = {a, aaaa,aaaaaaa,aaaaaaaaaaa ....} generated by (a⁴)* . So Regular 

2.  where i+j+k>100 & k>50 =  Regular restriction length should be atleast 101 in which c should be atleast 51.

3.  where i+j+k>100 & j+k>50 = Regular length sholud be ateast 101 and where Band c sum should be atleast 51.

D will be answer

----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

1.  where i+j - k>100 & k>50  then non regular 

2.  where i- j+k>100 & j+k>50 then non regular.

Comments

yes, finite can be any fixed value like "99999999999999999999999999" and finite automata works. All we have to see is does our required number of states is some finite value. i.e., if we can construct a finite automata- no need to actually construct it.

---

I don't understand b and c. Explain

---

For b, using a distinct state to count the number of i's followed by number of j's. Do this only upto count 50. Then again starts counting for k. if count goes above 100 accept. Also, keep a dead state for any invaid input. Similarly for c.