Pumping Lemma for Regular Languages

  The Pumping Lemma is generally used to prove a language is not regular.

  If a DFA or NFA machine can be constructed to exactly accept
  a language, then the language is a Regular Language.

  If a regular expression can be constructed to exactly generate the
  strings in a language, then the language is regular.

  If a regular grammar can be constructed to exactly generate the
  strings in a language, then the language is regular.

  To prove a language is not regular requires a specific definition of
  the language and the use of the Pumping Lemma for Regular Languages.

  A note about proofs using the Pumping Lemma:

  Given: Formal statements A and B.
         A implies B.
  If you can prove B is false, then you have proved A is false.

  For the Pumping Lemma, the statement "A" is "L is a Regular Language",
  The statement "B" is a statement from the Predicate Calculus.
  (This is a plain text file that uses words for the upside down A that
   reads 'for all'  and the backwards E that reads 'there exists')

   Formal statement of the Pumping Lemma:

   L is a Regular Language implies 
   (there exists n)(for all z)[z in L and |z|>=n implies
     {(there exists u,v,w)(z = uvw and |uv|<=n and |v|>=1 and
                                            
                           (for all i>=0)(uviw is in L) )}]

  The two commonest ways to use the Pumping Lemma to prove a language
  is NOT regular are:

  a) show that there is no possible n for the (there exists n),
     this is usually accomplished by showing a contradiction such
     as  (n+1)(n+1) < n*n+n

  b) show there is no way to partition z into u, v and w such that  
     uviw is in L, typically for a value i=0 or i=2.
     Be sure to cover all cases by argument or enumerating cases.

  Note: The pumping lemma only applies to languages (sets of strings)
  with infinite cardinality. A DFA can be constructed for any
  finite set of strings. Use the regular expression to NFA 'union'
  construction.
                                                            
  Notation: the string having n a's followed by  n b's is  an b n
  which is reduced to one line by writing  an bn

  Languages that are not regular:
  L = { an bn  n>0 }
  L = { a(n*n)  n>0 } also applies to n a prime(n log n), 2n, n!
  L = { an bk  n>0 k>n } can not save count of a's to check b's k>n
  L = { an bk+n n>0 k>1 } same language as above 

  Languages that are regular:
  L = { an  n>=0 } this is just  r = a*
  L = { an bk n>0 k>0 } no relation between n and k,  r = a a* b b* 
  L = { a(37*n+511) n>0 } 511 states in series, 37 states in loop