Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Possible Duplicate:
Pumping lemma for simple finite regular languages

The pumping lemma says that 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, \ldots$ constructed by repeating $y$ an arbitrary number of times (including zero times) are still in $L$.

Consider a regular Language which contains only one string - the alphabet $a$. ie, $L = \{a\}$.

Now, in this $L$, what would be the value of $p$, and possible values of $x$, $y$ , $z$?

I am confused to the boundary cases of the pumping lemma.

share|improve this question

migrated from cstheory.stackexchange.com Dec 7 '12 at 21:01

This question came from our site for theoretical computer scientists and researchers in related fields.

marked as duplicate by Ran G., Merbs, A.Schulz, sdcvvc, Realz Slaw Dec 10 '12 at 15:34

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

add comment

2 Answers 2

up vote 5 down vote accepted

The short answer is that for any finite language $p$ is greater than the length of every string in the language - i.e. finite languages are a trivial case as it's true that every string longer than $p$ can be pumped.

Beyond the question you asked, understanding what the pumping length is can help with stuff that you might do later. A very brief sketch of the proof of the lemma is that given a regular language, there's some DFA that accepts it. We can can take $p$ to be the number of states in that DFA.

Then if there are no loops in the DFA, we have a finite language an every string has length strictly less than $p$ (it can't have passed through the same state twice), this is the case in the question.

If there are loops (i.e. the language is infinite) then there can be strings of length greater than $p$, but this means that they have to have repeated some states (by going around the loop), and that it has to have done this loop in the first $p$ characters (otherwise we have too many characters for the number of states). This loop is the $y$ section of the string, obviously we can go around the loop as much as we want (even zero times), and this is the pumping part.

Obviously this is quite informal, but you should be able to glean the essential parts that give the conditions of the pumping lemma.

share|improve this answer
    
Thanks.. that cleared the doubt.. –  MIkhail Dec 7 '12 at 4:33
add comment

Short answer: Let $p = 10^{100}$. There are no strings of length $p$ in your language, so the conditions of the pumping lemma are vacuously satisfied.

share|improve this answer
add comment

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