Yet Another Example

Consider the language L = {aⁿ | 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 ≠ λ, |xy| ≤ |Q| and xy^kz ∈ L(M) for all k. Notice that 1 ≤ |y| ≤ |Q|)
   • set w' = xy⁰z (Notice that |xy⁰z| = |Q|² + 2|Q| + 1 - |y|, and since 1 ≤ |y| ≤ |Q| this means |Q|² < |xy⁰z| < (|Q| + 1)², 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 = \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!

This is really hard to prove using the pumping lemma! However, we don't need to work that hard, because we can leverage the languages we already proved are not regular. Here's a simple proof.

Let $L_{ab}$ be the language defined by the regular expression $a^*b^*$. Note that $\overline{L_{ne}}$ is the language of all strings with the same number of $a$s as $b$s. So $\overline{L_{ne}}\cap L_{ab} = \{a^n b^n\ \big|\ n\geq 0\}$. Assume, by way of contradiction, that there is a DFA $M$ that accepts $L_{ne}$. Then there's a DFA that accepts $\overline{L_{ne}}$. Since $L_{ab}$ is defined by a regular expression there is a DFA that accepts it as well. If we then apply the intersection algorithm for DFAs, we get a DFA that accepts $\overline{L_{ne}}\cap L_{ab} = \{a^n b^n\ \big|\ n\geq 0\}$, and that's a contradiction! So ... there is no DFA accepting $L_{eq}$.