Question About Pumping Lemma used on a FA

Question

I am learning about pumping lemma and I am trying to solve a problem. I need to use pumping lemma to show that: the Language L(M) defined by the following machine is infinite.

Here is the dfa:

Intuitively, the language accepted by the dfa above is because there are loops inside the dfa. However, I don't know how to formalize it by using pumping lemma.

This is what I have so far:

Let $n$ be the number of states in the dfa, where $n>0$.

Then, I am confused about how to pick a proper string s so that I can do the following:

Consider any choice of $u,v,w$ such that $s=uvw$, $|uv|\leq n, |v|\geq 1$. The construction implies that $uv$ must contain only 0s.

I'd appreciate if you can help!

Answer 1

When you have a regular language $\def\L{\mathscr L}\L$, the pumping lemma gives you a magic constant $p$, which in this case is at most 5, because you have an automaton for $\L$ that has 5 states. The magic constant has the property that if $s$ is any string in $\L$ that is at least $p$ characters long, then we can find arbitrarily long strings in $\L$ of a certain form. That is, if a regular language $\L$ contains even one long-enough string, then it must contain arbitrarily long strings as well.

Specifically, the pumping lemms says that if $|s|\ge p$, then there must be some way to divide $s$ into $u,v,w$ with $s=uvw$, where $|uv|\le p$ and $|v|\ge 1$ so that, for every $i$, the string $uv^iw$ is also in $\L$.

This is because, as you observed, a string $s$ with length $p$ or greater must go around a loop in the automaton, and we can let $u$ be the part before the loop, $v$ be the part that goes around the loop, and $w$ be the part after the loop, and then if the automaton is fed the string $uv^iw$ it will perform the same computation as for $s$, except that it will go around the loop $i$ times instead of exactly once, and will end at the same accepting state as for $s$.

So all you have to do is find a string $s$ from $\L$ that has length at least 5. Then you can utter the following mystical incantation:

“By the pumping lemma, there exist strings $u,v,w$ with $uvw = s$ and $|v|\ge 1$, such that for each $i\ge 0$, the string $uv^iw$ is also in $\L$. But since $|v|\ge 1$, the language $\{uv^iw \mid i\ge 0\}$ is infinite, and since this is a sublanguage of $\L$, the language $\L$ is infinite.”

Once you come up with a suitable $s$, you don't have to exhibit $u,v,$ or $w$ explicitly; the pumping lemma guarantees that they exist, which is all you need here. But it might be a useful exercise if you worked them out for yourself, in private, even though they are not required to answer the question.

I realize that nobody asked this, but I will remark anyway that it seems to me like a pretty dumb exercise—what you said originally, that the language is infinite because the DFA has loops, should be enough for anyone.

[ On further reflection, I realize it's not completely silly. One might have a DFA with a loop that is unreachable, or a loop from which there are no reachable accepting states, and such a DFA might accept a finite language in spite of the loop. So coming up with $s\in\L$ that travels the loop and ends at an accepting state is important ]