ex9-5.tex


1
2
3
4
5
6
7
8
9
10
11
12
13
14

\begin{solution}{5}
    \begin{enumerate}
        \item The intuition would be: for the first $a$ that we read, mark it with $X$ and mark the next $b$ we see with $Y$. Go back to the beginning and repeat. When we read a $Y$ instead of an $a$, we have finished the $a^i$ part of the string, and we can go to a final state. The machine should check that there is a $b$ for every $a$ and that the $a$s and $b$s are consecutive. 
            
            %todo draw machine

        \setcounter{enumi}{2}

        \item The intuition would be: find a $b$ for every $a$, mark both with $X$. Repeat until there are no $a$s left. Then check that there are also no $b$s left.

            %todo draw machine
    \end{enumerate}
\end{solution}