This problem shows that this exponential blowup in the number of states

is necessary. Let Asub$\{0,1{\}}^{**}$ be the set of all strings $($of length at least $101)$ that have

a $0$ exactly $100$ places from the right hand end. That is

$A=\{w$:$|w|101,w_{|w|-100}=0\}.$

$($a$)(5$ points$)$ Draw the state diagram for an NFA with $101102$ states that recognizes

A$.($You can use $"..."$ and don't have to draw all $101102$ states, as long as it's

clear what the states$/$transitions would be in the omitted states$)[$Ray: Update: I

think you need $102$ states. If you have $103$ or $104$ states, that's fine.$]$

$($b$)(10$ points$)$ Show that no DFA on less than $2^{100}$ states can recognize $A.$ Hint: ${?}^2$

${?}^1$ In this class, we learn several methods for proving a language $A$ is regular: constructing a DFA recog$-$

nizing $A,$ constructing an NFA recognizing $A,$ finding a regular expression for $A.$ However, we only learn

one method for proving a language is not regular. What is it$?$

${?}^2$ Give a proof by contradiction and assume such a DFA exists. Apply pigeonhole to all $2^{100}$ strings of

length $100$ to get two strings $x$ and $y$ of length $100$ that end up at the same state after digesting. Derive a

contradiction by considering the strings $xz$ and $yz$ for some carefully chosen string $z.$