Class 21: Pumping Lemma Reprise


Reading
Section 2.5 of Theory of Computing, A Gentle Introduction.
Homework
Then printout the homework and answer the questions on that paper.

Yet Another Example
Consider the language L = {an | n is a perfect square} Using the Pumping Lemma Version 2.0, design an algorithm with the following specification:
Input: machine M = (Q,Σ,δ,s,W
Output: string w' such that either w' ∈ L but w' ∉ L(M), or w' ∉ L but w' ∈ L(M).
The existence of such an algorithm proves that L can't be accepted by a finite automaton.
  1. let w = a(|Q| + 1)2 (Notice that w ∈ L)
  2. if M doesn't accept w then set w' = w
    else
    • let x, y and z be the strings guaranteed to exist by the Pumping Lemma Version 2.0. (i.e. w = xyz, y ≠ λ, |xy| ≤ |Q| and xykz ∈ L(M) for all k. Notice that 1 ≤ |y| ≤ |Q|)
    • set w' = xy0z (Notice that |xy0z| = |Q|2 + 2|Q| + 1 - |y|, and since 1 ≤ |y| ≤ |Q| this means |Q|2 < |xy0z| < (|Q| + 1)2, which in turn means w' is not a perfect square, and thus not in L. )
Either w'∈ L and M rejects it, or w' ∉ L but M accepts it. Either way, L(M) ≠ L.

Note: the important thing about this example is that it really shows you why proof requires justifying that the w' you get by pumping in the last step is guaranteed to give you a string that is not in the language L. While it's easy to follow the algorithm itself, it is not easy to see that it will always produce a string that the input machine misclassifies with respect to L. So without that justification it's hard to believe that the algorithm gives you a proof that no FA accepts L.

Question: What string does the proceeding algorithm/proof produce for input machine

Another in-class Excercise
You were asked to provide a proof that the language L = { u ∈ {a,b}* | # of a's in u = # of b's in u } is not regular, i.e. is not accepted by any finite automaton. Such a proof, like the examples above, are algorithms that take a machine as input and produce a string that the string mischaracterizes by either accepting it when it's not in L, or rejecting it when it is.

If we'd had time, we would have swapped proofs/algorithms for the above, and ran them on the following two machines to see what strings were produced:

Important Point: When you use the Pumping Lemma version 2.0 to get x, y and z, you cannot assume they're anything you want them to be. The Pumping Lemma will only give you strings x, y and z such that y corresponds to going around a cycle of states in M!


Christopher W Brown
Last modified: Mon Oct 19 17:23:53 EDT 2009