Below is the Pumping lemma as stated in Automata and Computability by (Dexter C. Kozen)
Let $A$ be a regular set. Then the following property holds of $A$:
There exist $k≥0$ such that for any string $x,y,z$ with $xyz \in A$ and $|y|≥k$, there exist strings $u,v,w$ such that $y=uvw$,$v\not=ε $, and for all $i≥0$, the string $xuv^iwx\in A$
Here are my questions:
Let $∑=\{1\}$ $A=\{1\}$. Clearly $A$, is regular. Now, applying the pumping lemma, let $x=1,y=ε,z=ε$ and so $1εε=1 \in A$, and $|y|=0$ so $k=0$ but there is no way to split $y$ such that $v \not = ε$. So, how is the pumping lemma valid for this regular set?
Also, we can think of $k$ as being the number of states, but a DFA cannot have $0$ states. So why is $k$ not required to be strictly greater than 0.
Perhaps you can help my understanding by applying the pumping lemma above to the language $\{1\}$ as well the language of the empty string. What do value does k have in these situations? What about x,y,z and u,v,w?
Best Answer
Suppose that $A$ is regular. The pumping lemma says that there is a $k$ such if $w\in A$ has length at least $k$, then $w$ can be pumped; it does not say that $A$ necessarily has any words of length $k$ or more. In fact it’s clear that if $A$ actually does have a word of length at least $k$, then pumping it will produce infinitely many words. Thus, if $A$ is finite, every word of $A$ must be shorter than $k$. In particular, for $A=\{1\}$ we can take $k$ to be any integer greater than $1$: $A$ will then satisfy the conclusion of the pumping lemma vacuously, since $A$ has no words of length $k$ or more. More generally, if $A$ is finite, and $k>\max\{|w|:w\in A\}$, then $A$ vacuously satisfies the conclusion of the pumping lemma, since it has no words long enough to be pumped.
The pumping lemma is really only interesting when $A$ is infinite.