1
$\begingroup$

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?

$\endgroup$
2
  • 1
    $\begingroup$ Which pumping lemma? The meaning of $p$ becomes apparent from the proof. $\endgroup$ – Raphael Jan 27 '17 at 17:55
  • $\begingroup$ 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! $\endgroup$ – Raphael Jan 27 '17 at 17:55
1
$\begingroup$

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.

$\endgroup$
0
-1
$\begingroup$

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.

$\endgroup$
4
  • 2
    $\begingroup$ "So p has to be equal or greater than number of states" -- proof needed. Shorter words can have cycles. $\endgroup$ – Raphael Jan 27 '17 at 17:55
  • $\begingroup$ This doesn't really answer the question. $\endgroup$ – Rick Decker Jan 27 '17 at 18:24
  • $\begingroup$ @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. $\endgroup$ – Ack. Jan 27 '17 at 19:30
  • $\begingroup$ No, you don't get to flip implications like that. $\endgroup$ – Raphael Jan 27 '17 at 19:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.