Class 23: Pumping Lemma Reprise


Reading
Section 2.5 of Theory of Computing, A Gentle Introduction.
Homework
  1. Prove that no finite automaton accepts the language L1 = { ucv ∈ {a,b,c}* | u,v ∈ {a,b}* and u is a substring of v }. Justify your proof - i.e. explain how you know that the string produced by your proof/algorithm is either in L1 but rejected by the input machine, or accepted by the input machine but not in L1.

    Example strings in L1: bbcbabbbba and abbcabaabbab and cabaab

  2. Prove that no finite automaton accepts the language L2 = { cucvc ∈ {a,b,c}* | u,v ∈ {a,b}* and u is a substring of v }. Justify your proof - i.e. explain how you know that the string produced by your proof/algorithm is either in L2 but rejected by the input machine, or accepted by the input machine but not in L2.

    Example strings in L2: cbbcbabbbbac and cabbcabaabbabc and ccabaabc

  3. Challenge Problem: Prove that no finite automaton accepts the language L3 = { c+ucvc ∈ {a,b,c}* | u,v ∈ {a,b}* and u is a substring of v }, where the "+" is our usual "1 or more occurences", as with Perl and egrep. Justify your proof - i.e. explain how you know that the string produced by your proof/algorithm is either in L3 but rejected by the input machine, or accepted by the input machine but not in L3.

    Example strings in L3: cccccbbcbabbbbac and cccabbcabaabbabc and ccabaabc


Yet Another Example
Consider the language L = {an | n is a perfect square} 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| + 1)2 (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. Notice that 1 ≤ |y| ≤ |Q|)
    • set w' = xy0z (Notice that |xy0z| = |Q|2 + 2|Q| + 1 - |y|, and since 1 ≤ |y| ≤ |Q| this means |Q|2 < |xy0z| < (|Q| + 1)2, which in turn means w' is not a perfect square, and thus not in L. )
Either 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

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.

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!


Christopher W Brown
Last modified: Fri Oct 22 13:18:34 EDT 2004