Given a DFA $\mathcal{M} = (S, \Sigma, q_0, \delta, F)$, is there an algorithm that finds the pumping length of $L(\mathcal{M}$)?

Question

This question has been bugging me for a while, and I'm curious what such an algorithm would look like, if it exists. My guess is that it does exist, but I'm not sure how it would look.

Answer 1

If you look at the proof of the pumping lemma, you’ll see that you can use for the pumping length $|S|$, the number of states in $\mathscr{M}$. There are algorithms to reduce $\mathscr{M}$ to the minimal DFA accepting $L(\mathscr{M})$, if you want the best possible value.