0
$\begingroup$

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: enter image description here

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!

$\endgroup$
2
$\begingroup$

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 ]

$\endgroup$
  • $\begingroup$ Thanks for your detailed explanation. That's very helpful. And I think I know what to do now. Especially thank your for asking my question when nobody else is answering it. And your prompt "come up with a suitable s" almost gives me an epiphany. $\endgroup$ – y123liu Feb 28 '14 at 5:22
  • $\begingroup$ @y123liu I'm glad I could help. $\endgroup$ – MJD Mar 4 '14 at 16:47

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.