\begin{frame}{Example continued} \vspace{-1ex} \begin{exampleblock}{} Consider the input word \alert{$aab \in L(M)$}. Then $n = 2p(3) + 1 = 7$. \begin{center}\vspace{-1.5ex} \begin{tikzpicture}[default,nodes={rectangle}] \mpause[1]{ \tilew{0}{0}{$\vphantom{W}\Box$}{}{}{} \tilew{1}{0}{$\vphantom{W}\Box$}{}{}{} \tilew{2}{0}{$\vphantom{W}\Box$}{}{}{} \tilew{3}{0}{$q_0,\!a$}{}{}{} \tilew{4}{0}{$a$}{}{}{} \tilew{5}{0}{$b$}{}{}{} \tilew{6}{0}{$\vphantom{W}\Box$}{}{}{} } \mpause{ \tilew{0}{1}{$\vphantom{W}\Box$}{}{$\vphantom{W}\Box$}{} \tilew{1}{1}{$\vphantom{W}\Box$}{}{$\vphantom{W}\Box$}{} \tilew{2}{1}{$\vphantom{W}\Box$}{}{$\vphantom{W}\Box$}{} \tilew{3}{1}{$b$}{\rotatebox{90}{$q_0,\!\raisebox{-2pt}{R}$}}{$q_0,\!a$}{} \tilew{4}{1}{$q_0,\!a$}{}{$a$}{\rotatebox{90}{$q_0,\!\raisebox{-2pt}{R}$}} \tilew{5}{1}{$b$}{}{$b$}{} \tilew{6}{1}{$\vphantom{W}\Box$}{}{$\vphantom{W}\Box$}{} } \mpause{ \tilew{0}{2}{$\vphantom{W}\Box$}{}{$\vphantom{W}\Box$}{} \tilew{1}{2}{$\vphantom{W}\Box$}{}{$\vphantom{W}\Box$}{} \tilew{2}{2}{$\vphantom{W}\Box$}{}{$\vphantom{W}\Box$}{} \tilew{3}{2}{$b$}{}{$b$}{} \tilew{4}{2}{$b$}{\rotatebox{90}{$q_0,\!\raisebox{-2pt}{R}$}}{$q_0,\!a$}{} \tilew{5}{2}{$q_0,\!b$}{}{$b$}{\rotatebox{90}{$q_0,\!\raisebox{-2pt}{R}$}} \tilew{6}{2}{$\vphantom{W}\Box$}{}{$\vphantom{W}\Box$}{} } \mpause{ \tilew{0}{3}{$\vphantom{W}\Box$}{}{$\vphantom{W}\Box$}{} \tilew{1}{3}{$\vphantom{W}\Box$}{}{$\vphantom{W}\Box$}{} \tilew{2}{3}{$\vphantom{W}\Box$}{}{$\vphantom{W}\Box$}{} \tilew{3}{3}{$b$}{}{$b$}{} \tilew{4}{3}{$q_1,\!b$}{\rotatebox{90}{$q_1,\!\raisebox{-2pt}{L}$}}{$b$}{} \tilew{5}{3}{$b$}{}{$q_0,\!b$}{\rotatebox{90}{$q_1,\!\raisebox{-2pt}{L}$}} \tilew{6}{3}{$\vphantom{W}\Box$}{}{$\vphantom{W}\Box$}{} } \mpause{ \tilew{0}{4}{$\vphantom{W}\Box$}{}{$\vphantom{W}\Box$}{} \tilew{1}{4}{$\vphantom{W}\Box$}{}{$\vphantom{W}\Box$}{} \tilew{2}{4}{$\vphantom{W}\Box$}{}{$\vphantom{W}\Box$}{} \tilew{3}{4}{$b$}{}{$b$}{} \tilew{4}{4}{$q_1,\!b$}{}{$q_1,\!b$}{} \tilew{5}{4}{$b$}{}{$b$}{} \tilew{6}{4}{$\vphantom{W}\Box$}{}{$\vphantom{W}\Box$}{} } \mpause{ \tilew{0}{5}{$\vphantom{W}\Box$}{}{$\vphantom{W}\Box$}{} \tilew{1}{5}{$\vphantom{W}\Box$}{}{$\vphantom{W}\Box$}{} \tilew{2}{5}{$\vphantom{W}\Box$}{}{$\vphantom{W}\Box$}{} \tilew{3}{5}{$b$}{}{$b$}{} \tilew{4}{5}{$q_1,\!b$}{}{$q_1,\!b$}{} \tilew{5}{5}{$b$}{}{$b$}{} \tilew{6}{5}{$\vphantom{W}\Box$}{}{$\vphantom{W}\Box$}{} } \mpause{ \tilew{0}{6}{$\vphantom{W}\Box$}{}{$\vphantom{W}\Box$}{} \tilew{1}{6}{$\vphantom{W}\Box$}{}{$\vphantom{W}\Box$}{} \tilew{2}{6}{$\vphantom{W}\Box$}{}{$\vphantom{W}\Box$}{} \tilew{3}{6}{$b$}{}{$b$}{} \tilew{4}{6}{$q_1,\!b$}{}{$q_1,\!b$}{} \tilew{5}{6}{$b$}{}{$b$}{} \tilew{6}{6}{$\vphantom{W}\Box$}{}{$\vphantom{W}\Box$}{} } \end{tikzpicture}\vspace{-2ex} \end{center} \pause\pause\pause\pause\pause\pause\pause \alert{Complete tiling} of the $7 \times 7$ field. \end{exampleblock} \end{frame} \themex{Satisfiability Problem}