language

Question

L = { a^p b^q |0<=p<=1000<=q}

is it regular?

Answer 1

yes,because in this question power of a is going to be a finite no that can be stated in finite no of states,and value of q needs to be greater than that finite no that we can do easily by remembering no states while counting power of a.

so this problem is solvable in finite no of states or using dfa so its grammar is regular because every regular language can be transformed into dfa.

Comments

so for q it would be just one state greater than the number of states for p

and that state will have a self loop right?

---

No because p may be 1000. Then value of both p & q can be 1000. Value of P >1000 goes to nonaccepting state.

Max no of states can be 1000 for this FA.