**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^{(|Q|+1)^2}$
(Notice that
*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 $w = a^{(|Q|+1)^2}$
(Notice that
**Another in-class Excercise**-
You were asked to provide a proof that the language
$L = \left\{
u \in \{a,b\}^*\ \middle|\
|\text{# of $a$'s in $u$ - # of $b$'s in $u$}| \leq 2
\right\}$.
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 had time, we 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*! **Food for thought**- Here's a challenge: is the language $L_{ne} = \{ u \in \{a,b\}^* \ |\ \text{# $a$'s in $u$ $\neq$ # of $b$'s in $u$} \}$ a regular language? Whatever your answer, prove it!

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