Proving a regular language to be infinite

From: Mark \(The WannaBe\) (mark_hsn_at_hotmail.com)
Date: 10/16/04 

Date: Sat, 16 Oct 2004 10:07:55 +0200

Hi

I lost my head on this on. I both have the problem statement and the
solution, but I do not understand how the solution can be applied. I have
tried to come up with my reasoning for why the solution given by the book is
true, but I do not know if my reasoning is correct. The problem and the
solution of the book are given between the lines, --#--#--. The problem is
the same as problem 4.3.1 from "Introduction to Automata Theory, Languages,
and Computation" by Hopcroft et al. The solution is also given online here:
http://www-db.stanford.edu/~ullman/ialcsols/sol4.html.

--#--#--
Problem statement:
Give an algorithm to tell whether a regular language L is infinite.
Hint: Use the pumping lemma to show that if the language contains any string
whose length is above a certain lower limit, then the language must be
infinite.

The solution given by the book:
Let n be the pumping-lemma constant. Test all strings of length between n
and 2n-1 for membership in L. If we find even one such string, then L is
infinite. The reason is that the pumping lemma applies to such a string,
and it can be ``pumped'' to show an infinite sequence of strings are in L.

Suppose, however, that there are no strings in L whose length is in the
range n to 2n-1. We claim there are no strings in L of length 2n or more,
and thus there are only a finite number of strings in L. In proof, suppose w
is a string in L of length at least 2n, and w is as short as any string in L
that has length at least 2n. Then the pumping lemma applies to w, and we can
write w = xyz, where xz is also in L. How long could xz be? It can't be as
long as 2n, because it is shorter than w, and w is as short as any string in
L of length 2n or more. n, because xz is at most n shorter than w. Thus, xz
is of length between n and 2n-1, which is a contradiction, since we assumed
there were no strings in L with a length in that range.
--#--#--

To prove that a regular language were infinite then one way would be to
create a DFA accepting that language and then see if the DFA contained any
loops. This is where the PL comes in as I see it, because if the PL applies
for a regular language L then L will also be accepted by a DFA having at
least one loop. So I guess that the problem can be reformulated to prove
whether the pumping-lemma applies for a given regular language. Can the
problem statement be reformulated like this at all?

I think I can follow the prove given by the book for the existence of a
string whose length is in the range n to 2n-1 if the pumping-lemma applies.
Because the prove let n be the PL constant and then choose a PL string w
from L having a length |w|>=2n and because |w|>=n then the PL applies. Then
according to the rules of the PL w is broken into three string x, y, z i.e.
w = xyz where |y|>0 and where the string xz would also be in L. We know that
|y|>0 and because of that then |xz|<|w| i.e. that |xz|<2n and because
0<|y|<=|n| and |w|-|y|<|xz|<2n then n<|xz|<2n. So if PL applies then there
must exist a string, xz, with a length in the range n to 2n-1, which would
be in L, otherwise we would have a contradiction with our assumption that
the pumping-lemma applied for that language.

But I cannot see how this knowledge can be used in practice as a test for
whether the pumping-lemma applies and therefore for whether a language is
infinite? Is guess the process is something about choosing a string w of
length |w|>= 2n where n is the pumping-lemma constant and then show the
existence of another string in L in the range n to 2n-1? If this were done
for selected values of n and not for all n>=1 then this approach could prove
finite languages to be infinite, so this cannot be the way to do it? If this
is to be done for all n >=1 then I cannot see how this solution is different
from just testing whether the pumping-lemma applies using the usual
approach? With the usual approach I mean, let n be the pumping-lemma
constant, choose a string w belonging to L where |w|>=n and then break the
string into x, y and z where w = xyz and see if you can construct new
strings of L by pumping up y.

I am sure I am missing a point somewhere. Can anyone point out for me what
it is that I do not see in the solution given above? How can the solution
given by the book be used to test for infinity of regular languages?

Kind regards
Mark (The WannaWannaBe of Computer Science)

Relevant Pages

  • Re: Operator overloading in C
    ... All development of C as an independent language has ... making any changes or improvements to the standard ... The lack of a counted string data structure, ... Pointers can't be used for arg1 or arg2. ...
    (comp.std.c)
  • Re: syntax...
    ... B&D on the part of the language designer. ... probably handle concatenation of string literals by itself, ... bitwise XOR, or if not that, then exponentiation.) ...
    (comp.lang.misc)
  • Why C Is Not My Favourite Programming Language
    ... C has no string type. ... compiler take care of the rest. ... Why does any normal language ... the programmer fail. ...
    (comp.lang.c)
  • Re: Controlling Javascript from server side
    ... but five different language implementations here. ... 'true' means that the request must be handled asynchronously. ... There is exactly *no* reason for such a thing here. ... | percent-endoded string). ...
    (comp.lang.javascript)
  • Re: Theodore Adorno, a prophet of data systems design
    ... C may not be a forgiving language, ... >> attention get burned with the memory leaks, and buffer overruns, ... by a small, compact team of brilliant programmers, or it may be ... so you agree that it is not a limit on the length of the string, ...
    (comp.programming)