Class 20: Pumping Lemma II

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

Deterministic vs. non-Deterministic
Our proof of the pumping lemma last class relied on the following: In processing a string of length at least |Q| we will find a non-empty "loop" in the computation, i.e. we will visit some state twice and, in between visits, will have read at least one symbol from the input. With non-deterministic machines, the only problem is that we might find a "loop" that only involved taking λ-transitions. Can we argue that we can always find a loop involving at least one non-λ-transition? Yes, it just takes a modicum more thought.

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 proceeded 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 λ!

Strengthening the Pumping Lemma (Machine Version 2.0)
From last class's homework assignment, you hopefully concluded that for machine M = (Q,Σ,δ/Δ,s,W) it's always possible to decompose a string w ∈ L(M), where |w| ≥ |Q|, into x, y and z satisfying xykz in such a way that |xy| ≤ |Q|. In other words, there will always be at least one loop within the first |Q| characters. This allows us to strengthen the Pumping Lemma to the following:
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 ≠ e and |xy| ≤ the number of states in M, such that xykz ∈ L(M) for all k.
This new, stronger version of the Pumping Lemma makes it a whole bunch easier to prove that languages can't be accepted by FAs.

Example using the Pumping Lemma Version 2.0

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

 Proof with Version 1.0 Proof with Version 2.0 Consider the following algorithm: Algorithm A Input: DFA M = (Q,Σ,δ,s,W), where Σ = {a,b} Output: string w' ∈ Σ* that M misclassifies with respect to L = {anbn| n ≥ 0}, i.e. either w' ∈ L but w' ∉ L(M) or w' ∉ L but w' ∈ L(M) let w = a|Q|b|Q| if w is not accepted by M then set w' = w (w' should be accepted, but isn't!) else let x,y,z be the strings produced by the Pumping Lemma for machine M and string w. set w' = xy2z (w' shouldn't be accepted, but is!) We claim that w' is misclassified by M with respect to L. Why? First note that w ∈ L, and |w| ≥ |Q|. If w ∉ L(M) then M clearly misclassifies w and we set w' = w. Otherwise, we satisfy the first two conditions in the Pumping Lemma v1.0, so we get our x, y and z and set w' = xy2z. By the Pumping Lemma, M accepts w'. However, w' ∉ L. Why? if y is entirely within the a's block of w, then xy2z will have more a's than b's and thus won't be in L. if y is entirely within the b's block of w, then xy2z will have more b's than a's and thus won't be in L. if y straddles the a's block and the b's block, then xy2z will have some a's coming after b's and thus won't be in L. Whichever is the case, M misclassifies w', and our thereom is proved. Consider the following algorithm: Algorithm A Input: DFA M = (Q,Σ,δ,s,W), where Σ = {a,b} Output: string w' ∈ Σ* that M misclassifies with respect to L = {anbn| n ≥ 0}, i.e. either w' ∈ L but w' ∉ L(M) or w' ∉ L but w' ∈ L(M) let w = a|Q|b|Q| if w is not accepted by M then set w' = w (w' should be accepted, but isn't!) else let x,y,z be the strings produced by the Pumping Lemma for machine M and string w. set w' = xy2z (w' shouldn't be accepted, but is!) We claim that w' is misclassified by M with respect to L. Why? First note that w ∈ L, and |w| ≥ |Q|. If w ∉ L(M) then M clearly misclassifies w and we set w' = w. Otherwise, we satisfy the first two conditions in the Pumping Lemma v2.0, so we get our x, y and z and set w' = xy2z. By the Pumping Lemma, M accepts w' and since |xy| ≤ |Q|, y consists solely of a's. Thus, xy2z has more a's than b's, and therefore is not in L.

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.

Example 1
Consider the language L of all palindromes over {a,b}. [Note: a palindrome is a string that reads the same forwards as backwards.] 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|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 ≠ e, |xy| ≤ |Q| and xykz ∈ L(M) for all k.)
• set w' = xy2z (Notice that this isn't a palindrome. Why? Because y came from the first |Q| characters of w, so w'= xy2z = amban, where m > n, which isn't a palindrome.)
Either w' = a|Q|ba|Q|, which is a palindrome, and M rejects it, or w'= xy2z = amban, where m > n, which isn't a palindrome, but which M accepts. Either way, L(M) ≠ L.

Note: In class we tried this same thing with w = a⌊|Q|/2⌋ba⌊|Q|/2⌋ and we found that, running it on one example machine, the algorithm did not always produce counterexamples. That was a very important (and hopefully illuminating) exercise!

Example 2
Consider the language L = {ai:aj:am ∈ {a,:}*| m = i + j} 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|:a|Q|:a2|Q| (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 ≠ e, |xy| ≤ |Q| and xykz ∈ L(M) for all k.)
• set w' = xy0z (Notice that since y came from the first |Q| characters of w, xy0z = a|Q|-|y|:a|Q|:a2|Q|, and since y ≠ e this means w' ∉ L. )
Either w'∈ L and M rejects it, or w' ∉ L but M accepts it. Either way, L(M) ≠ L.

Example 3
Consider the language L of all valid prefix expressions over {+,-,*,a,b,c}. [Ex: `+ * c - a c b` is valid, whereas `- a b c + d *` is not.] 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 = +|Q|a|Q|+1 (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 ≠ e, |xy| ≤ |Q| and xykz ∈ L(M) for all k.)
• set w' = xy3z (Notice that since y came from the first |Q| characters of w it consists of one or more + symbols. Thus, w' = xy3z has more operators than operands, and is not a valid prefix expression. This means w' ∉ L. )
Either w'∈ L and M rejects it, or w' ∉ L but M accepts it. Either way, L(M) ≠ L.

Christopher W Brown