**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 = {a*is a perfect square^{n}| n*}*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)*.*L*can't be accepted by a finite automaton.- let
*w = a*(Notice that^{(|Q| + 1)2}*w ∈ L*) - 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*xy*for all^{k}z ∈ L(M)*k*. Notice that*1 ≤ |y| ≤ |Q|*) - set
*w' = xy*(Notice that^{0}z*|xy*, and since^{0}z| = |Q|^{2}+ 2|Q| + 1 - |y|*1 ≤ |y| ≤ |Q|*this means*|Q|*, which in turn means^{2}< |xy^{0}z| < (|Q| + 1)^{2}*w'*is not a perfect square, and thus not in*L*. )

- let

*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

- let
**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