Question

Let Σ= {a}, assume language, L= { a^(2012.K)  / K> 0}, what is minimum number of states needed in a DFA to recognize L

Answer 1

States are 2013..

from S0 to S2012.. S2012 is final state, S0 is starting..

transition from S0--->S1--->......S2012 ---> S1..

Comments

@digvijay

Please suggest why in your solution last transition is from S2012-->S1?

What is the significance of 'k' in the question?

Please suggest.

---

if you are not able to understand this question let reduce it for example instead of 2012 consider this language$a^{3k}$ then transition will be so->s1->s2->s3(final state)->s1 {for different value of k it will enter in the loop}.

---

In this question if the value of k=2 then it repeats the loop twice ??? is it true??

Answer 2

L={a^nk / k>0} (n is constant) require n+1 states (from (S1 to Sn) + S0