The Pumping Lemma is generally used to prove a language is not regular. If a DFA, NFA or NFA-epsilon 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 i (for all i>=0)(uv w 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 a way to partition z into u, v and w such that i uv w is not in L, typically by pumping a value i=0, i=1, or i=2. i Stop as soon as one uv w is not in the language, thus, you have proved the language is not regular. 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. n n Notation: the string having n a's followed by n b's is a b which is reduced to one line by writing a^n b^n Languages that are not regular: L = { a^n b^n n>0 } L = { a^f1(n) b^f2(n) n<c } for any non degenerate f1, f2. L = { a^f(n) n>0 } for any function f(n)< k*n+c for all constants k and c L = { a^(n*n) n>0 } also applies to n a prime(n log n), 2^n, n! L = { a^n b^k n>0 k>n } can not save count of a's to check b's k>n L = { a^n b^k+n n>0 k>1 } same language as above Languages that are regular: L = { a^n n>=0 } this is just r = a* L = { a^n b^k 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

### Basis of proofs

You may be proving a lemma, a theorem, a corollary, etc A proof is based on: definition(s) axioms postulates rules of inference (typical normal logic and mathematics) To be accepted as "true" or "valid" Recognized people in the field need to agree your definitions are reasonable axioms, postulates, ... are reasonable rules of inference are reasonable and correctly applied "True" and "Valid" are human intuitive judgments but can be based on solid reasoning as presented in a proof. Types of proofs include: Direct proof (typical in Euclidean plane geometry proofs) Write down line by line provable statements, (e.g. definition, axiom, statement that follows from applying the axiom to the definition, statement that follows from applying a rule of inference from prior lines, etc.) Proof by contradiction: Given definitions, axioms, rules of inference Assume Statement_A use proof technique to derive a contradiction (e.g. prove not Statement_A or prove Statement_B = not Statement_B, like 1 = 2 or n > 2n) Proof by induction (on Natural numbers) Given a statement based on, say n, where n ranges over natural numbers Prove the statement for n=0 or n=1 a) Prove the statement for n+1 assuming the statement true for n b) Prove the statement for n+1 assuming the statement true for n in 1..n Prove two sets A and B are equal, prove part 1, A is a subset of B prove part 2, B is a subset of A Prove two machines M1 and M2 are equal, prove part 1 that machine M1 can simulate machine M2 prove part 2 that machine M2 can simulate machine M1 Limits on proofs: Godel incompleteness theorem: a) Any formal system with enough power to handle arithmetic will have true theorems that are unprovable in the formal system. (He proved it with Turing machines.) b) Adding axioms to the system in order to be able to prove all the "true" (valid) theorems will make the system "inconsistent." Inconsistent means a theorem can be proved that is not accepted as "true" (valid). c) Technically, any formal system with enough power to do arithmetic is either incomplete or inconsistent.