What exactly is the 'pumping length' in the Pumping lemma?
I'm trying to understand what is this 'margical' number 'n' that is used
in every application of the Pumping lemma. After hours of research on the
subject, I came to this website -->
http://elvis.rowan.edu/~nlt/TheoryNotes/PumpingLemma.pdf
that states
Processing z requires tracing a path of |z| edges ¡ª thus |z|+1 nodes ¡ª
through the FA graph (one arc per symbol in z). q0 q1 q2 ... qlength(z)
The FA has some finite number of states ¡ª say, s. If |z| ¡Ý s, then
some state must occur twice in the above sequence ¡ª thus, the sequence
contains a loop. If there¡¯saloop, then you could go around the loop as
many times as you wanted and still get strings in L. n is the longest a
string can be without having a loop. The biggest n can be is s, though it
might be smaller for some particular language.
From what I understand if there is a Language L then the pumping length of
L is the amount of states in the Finite State Automata that recognizes L.
Is this true?
If it is then what exactly does the last line from above say "though it
might be smaller for some particular language" ?? Complete mess in my
head. Could somebody clear it up, please?
No comments:
Post a Comment