Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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?
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.
