\begin{frame}{Pumping Lemma as a Game} \begin{goal}{} To \emph{contradict the pumping property}, we prove the negation: \begin{talign} &\alert{\forall} m>0.\\[-.5ex] &\qquad \alert{\exists} w\in L \text{ with } |w|\geq m.\\[-.5ex] &\qquad\qquad \alert{\forall} x,y,z \text{ with } w=xyz,\; |xy| \leq m,\; |y|\geq 1.\\[-.5ex] &\qquad\qquad\qquad \alert{\exists} i \geq 0.\, xy^iz \alert{\not\in} L \end{talign} \end{goal} \begin{block}{Pumping Lemma as a Game} Given is a language $L$. \pause We want to prove that $L$ is not regular. \begin{enumerate} \pause \item Opponent picks \alert{$m$}. \pause \item We choose a word \alert{$w\in L$} with $|w|\geq m$. \pause \item Opponent picks \alert{$x,y,z$} with $w=xyz$, $|xy|\leq m$ and $|y|\geq 1$. \pause \item If we can find \alert{$i\geq 0$} such that \alert{$xy^iz\not\in L$}, then \emph{we win}. \end{enumerate} \pause If we can always win, $L$ does not have the pumping property! \end{block} \pause \begin{exampleblock}{} Who wins the game when $L$ is finite? \end{exampleblock} \end{frame}