**Reading**-
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 we 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*xy*in such a way that^{k}z*|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 ≠ λ*and*|xy| ≤*the number of states in*M*, such that*xy*for all^{k}z ∈ L(M)*k*. **Example using the Pumping Lemma Version 2.0**-
**Theorem:**There is no deterministic finite automaton accepting*L = {a*.^{n}b^{n}| 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 = {a*, i.e. either^{n}b^{n}| n ≥ 0}*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!)

- let
*x,y,z*be the strings produced by the Pumping Lemma for machine*M*and string*w*. - set
*w' = xy*(^{2}z*w'*shouldn't be accepted, but is!)

- set

*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' = xy*. By the Pumping Lemma,^{2}z*M*accepts*w'*. However,*w' ∉ L*. Why?- if
*y*is entirely within the*a*'s block of*w*, then*xy*will have more^{2}z*a*'s than*b*'s and thus won't be in*L*. - if
*y*is entirely within the*b*'s block of*w*, then*xy*will have more^{2}z*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*xy*will have some^{2}z*a*'s coming after*b*'s and thus won't be in*L*.

*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 = {a*, i.e. either^{n}b^{n}| n ≥ 0}*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!)

- let
*x,y,z*be the strings produced by the Pumping Lemma for machine*M*and string*w*. - set
*w' = xy*(^{2}z*w'*shouldn't be accepted, but is!)

- set

*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' = xy*. By the Pumping Lemma,^{2}z*M*accepts*w'*and since |*xy*| ≤ |*Q*|,*y*consists solely of*a*'s. Thus,*xy*has more^{2}z*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.

- let
**Example 1**-
Consider the language
$L_p$ 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_p$*but*w' ∉ L(M)*, or*w' ∉ $L_p$*but*w' ∈ L(M)*.- let
*w = a*(Notice that^{|Q|}ba^{|Q|}*w*is a palindrome!) - 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*xy*for all^{k}z ∈ L(M)*k*.) - set
*w' = xy*(Notice that this isn't a palindrome. Why? Because^{2}z*y*came from the first*|Q|*characters of*w*, so*w'= xy*, where^{2}z = a^{m}ba^{n}*m > n*, which isn't a palindrome.)

- let

*w' = a*, which is a palindrome, and^{|Q|}ba^{|Q|}*M*rejects it, or*w'= xy*, where^{2}z = a^{m}ba^{n}*m > n*, which isn't a palindrome, but which*M*accepts. Either way,*L(M) ≠ $L_p$*.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 one example machine, the algorithm did not always produce counterexamples. That was a very important (and hopefully illuminating) exercise!

- let
**Example 2**-
Consider the language
*$L_s$ = {a*Using the Pumping Lemma Version 2.0, design an algorithm with the following specification:^{i}:a^{j}:a^{m}∈ {a,:}*| m = i + j}**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)*.*L*can't be accepted by a finite automaton.- let
*w = a*(Notice that^{|Q|}:a^{|Q|}:a^{2|Q|}*w ∈ $L_s$*) - 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*.) - set
*w' = xy*(Notice that since^{0}z*y*came from the first*|Q|*characters of*w*,*xy*, and since^{0}z = a^{|Q|-|y|}:a^{|Q|}:a^{2|Q|}*y ≠ λ*this means*w' ∉ $L_s$*. )

- let

*w'∈ $L_s$*and*M*rejects it, or*w' ∉ $L_s$*but*M*accepts it. Either way,*L(M) ≠ $L_s$*. - let
**Example 3**-
A "prefix expression" is an expression in which the operator
appears
*before*it's operands, e.g. we write "+ 4 7" instead of "4 + 7", as we would with infix expressions. So, for example, "* 4 - 7 2" would be "4 * (7 - 2)". Consider the language $L_X$ 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_X$*but*w' ∉ L(M)*, or*w' ∉ $L_X$*but*w' ∈ L(M)*.*L*can't be accepted by a finite automaton.- let
*w = +*(Notice that^{|Q|}a^{|Q|+1}*w ∈ $L_X$*) - 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*.) - set
*w' = xy*(Notice that since^{3}z*y*came from the first*|Q|*characters of*w*it consists of one or more + symbols. Thus,*w' = xy*has more operators than operands, and is not a valid prefix expression. This means^{3}z*w' ∉ $L_X$*. )

- let

*w'∈ $L_X$*and*M*rejects it, or*w' ∉ $L_X$*but*M*accepts it. Either way,*L(M) ≠ $L_X$*. - let

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