# p constant in pumping lemma for regular languages

We have a language

$L = \{ a^{n^{2}}, n < 12\}$ We have to find minimum constant P for pumping lemma.

What does p represent here? I thought p in pumping lemma represent number of states , yet the right answer is $p >= 122$ , i would understand if it was $p <= 122$.

So for example it would be correct when $p = 155$. But how could we create such automat with 155 states?

• Which pumping lemma? The meaning of $p$ becomes apparent from the proof.
– Raphael
Jan 27, 2017 at 17:55
• The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you!
– Raphael
Jan 27, 2017 at 17:55

The key here is that $L$ is a finite language. Therefore it can be recognized by a DFA which has no cycles - in this case, a chain of 122 states, numbered 1 through 122, with transitions on $a$ from each state $i$ to state $i+1$ [except for a loop on $a$ from state 122 to itself], with states 1, 4, 9, ..., 121 being final. For P=122, this automaton satisfies the Pumping Lemma - i.e all strings in $L$ of length at least P can be pumped - in a purely vacuous sense, because there are no strings in $L$ of length at least P.

From Wikipedia:

for any regular language L there exists a constant p such that any word w in L with length at least p can be split into three substrings, w = xyz, where the middle portion y must not be empty, such that the words xz, xyz, xyyz, xyyyz, … constructed by repeating y zero or more times are still in L.

So p has to be equal or greater than number of states. If you choose a word w with length < number of states, you will have no cycles in the path from initial state to final state determined by w, and then you can't find (for every division of w in xyz, with |xy|<=p and |y|>=1) a substring y which you can remove from w (or multiply as many times as you want) obtaining a new word w' in L.

• "So p has to be equal or greater than number of states" -- proof needed. Shorter words can have cycles.
– Raphael
Jan 27, 2017 at 17:55
• This doesn't really answer the question. Jan 27, 2017 at 18:24
• @Raphael "Shorter words can have cycles" you're right, but the Pumping Lemma regards any word w in L with length at least p, so you can choose a word w with length < number of states with no cycles -> p has to be equal or greater than number of states.
– Ack.
Jan 27, 2017 at 19:30
• No, you don't get to flip implications like that.
– Raphael
Jan 27, 2017 at 19:34