Problem 1

Show that the language L = {aⁿ | n is a perfect square} is not regular (i.e. no DFA/NDFA accepts it, no R.E. defines it).

Algorithm
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).

1. let $w = a^{(|Q|+1)^2}$
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.
   • set w' = xy⁰z

Note: it is not at all obvious that this algorithm meets its specification! We will discuss later!

Question: What string does the proceeding algorithm/proof produce for input machine

Problem 2

Break up into groups of three and:

Prove 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.

Note: This will require producing an algorithm that takes a machine as input and produces a string that the machinge mischaracterizes by either accepting it when it's not in L, or rejecting it when it is.

Problem 3

Swap boards with another group, and try running the algorithm they came up with on the following two machines: