Consider running string w through machine M = (Q,Σ,Δ,s,W). Write out the computation as a sequence of states separated by the input symbol read (or λ) as we did last class. Now, circle the initial state in the list, and all states directly preceeded by reading a symbol - i.e. not λ. There must be more than |Q| circled states in the list, so we can find repetitions. The whole subsequence between these repeated occurences is a loop in the computation, and the loop contains at lease one non-λ-transition. After all, the last state in the loop is circled, and that means it is immediately proceeded by a symbol from the alphabet, i.e. not λ!

The Pumping Lemma (Machine Version 2.0)
For any finite automaton M, for all w ∈ L(M) of length greater than or equal to the number of states in M, there exist x,y,z ∈Σ*, where w = xyz and y ≠ λ and |xy| ≤ the number of states in M, such that xy^kz ∈ L(M) for all k.

Theorem: There is no deterministic finite automaton accepting L = {aⁿbⁿ| n ≥ 0}.

Here the big benefit of using V2.0 is that that justification for the algorithm is easier. Why? Because we don't have as many cases to consider. In other problems, V2.0 even makes the algorithms themselves easier.

Input: machine M = (Q,Σ,δ,s,W)
Output: string w' such that either w' ∈ $L_p$ but w' ∉ L(M), or w' ∉ $L_p$ but w' ∈ L(M).

1. let w = a^|Q|ba^|Q| (Notice that w is a palindrome!)
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 xy^kz ∈ L(M) for all k.)
   • set w' = xy²z (Notice that this isn't a palindrome. Why? Because y came from the first |Q| characters of w, so w'= xy²z = a^mbaⁿ, where m > n, which isn't a palindrome.)

Note: In class we tried this same thing with $w = a^{\lfloor |Q|/2 \rfloor}b^{\lfloor |Q|/2 \rfloor}$ and we found that, running it on the example machine below, the algorithm did not always produce counterexamples. That was a very important (and hopefully illuminating) exercise!

Input: machine M = (Q,Σ,δ,s,W)
Output: string w' such that either w' ∈ $L_s$ but w' ∉ L(M), or w' ∉ $L_s$ but w' ∈ L(M).

1. let w = a^|Q|:a^|Q|:a^2|Q| (Notice that w ∈ $L_s$)
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 xy^kz ∈ L(M) for all k.)
   • set w' = xy⁰z (Notice that since y came from the first |Q| characters of w, xy⁰z = a^|Q|-|y|:a^|Q|:a^2|Q|, and since y ≠ λ this means w' ∉ $L_s$. )

Input: machine M = (Q,Σ,δ,s,W)
Output: string w' such that either w' ∈ $L_X$ but w' ∉ L(M), or w' ∉ $L_X$ but w' ∈ L(M).

1. let w = +^|Q|a^|Q|+1 (Notice that w ∈ $L_X$)
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 xy^kz ∈ L(M) for all k.)
   • set w' = xy³z (Notice that since y came from the first |Q| characters of w it consists of one or more + symbols. Thus, w' = xy³z has more operators than operands, and is not a valid prefix expression. This means w' ∉ $L_X$. )