0

How do you determine the minimum pumping length for some machine in graph form?

let's there are 7 states – $q_0$, $q_1$, $q_2$, $q_3$, $q_4$, $q_5$, $q_6$ in a deterministic machine. The arrows can flow in any direction.

$q_6$ and $q_3$ are both accept states.

How would I calculate the minimum pumping length with just this information? Thank you

J.-E. Pin
  • 40,163
internetuser
  • 1

1 Answers1

0

You can't find the minimum pumping length with this information. To start with, if your automaton recognizes a finite language, there is no pumping length at all. If it recognizes an infinite language, then the number of states of the automaton is an upper bound of the pumping length, but the minimum pumping length might be smaller.

J.-E. Pin
  • 40,163