\documentclass[11pt,a4paper]{book}

\usepackage[portuguese]{babel}
\usepackage{verbatim}
\usepackage{fullpage}
\pagestyle{empty}
\usepackage{gastex}
\usepackage[usenames]{color}

\newcounter{conta}
\pagestyle{empty}

\begin{document}
 
\vspace*{15mm}
\noindent P\'os-Gradua\c{c}\~ao em Ci\^{e}ncia da Computa\c{c}\~{a}o
 \hfill DCC/ICEx/UFMG \\
\noindent {\it Teoria de Linguagens}
 \hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2008 \\
\noindent Professor: Newton Jos\'{e} Vieira \\
\noindent {\bf Prova Suplementar} \hfill 10/12/2008

\vspace*{3mm}
\begin{flushleft}
Dura\c{c}\~ao: 1 hora e 30 minutos.
\end{flushleft}

\begin{flushleft}
Cada item de cada quest\~ao vale \textbf{3 pontos}.
\end{flushleft}

\begin{enumerate}
 \item Construa:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item um AFD,
        \item uma express\~ao regular, e
        \item uma gram\'atica regular
       \end{list}
       para a linguagem $\{w\in \{{\tt 0},{\tt 1}\}^*\,|\, w \mbox{ cont\'em {\tt 11} e todo {\tt 0} \'e seguido de
       {\tt 1}}\}$. No item (a), apenas desenhe o diagrama de estados. No item (b), n\~ao ser\~ao aceitas
       express\~oes regulares com sintaxe incorreta.

 \item Seja a gram\'atica $G=(\{S,A\},\{{\tt 0},{\tt 1}\},R,S)$ em que $R$ consta das regras:
       \begin{enumerate}
        \item[\ ] $S\,\rightarrow\,{\tt 0}A \,|\, S{\tt 1}$
        \item[\ ] $A\,\rightarrow\, S{\tt 1} \,|\, {\tt 1}$
       \end{enumerate}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Descreva a linguagem $L(G)$.
        \item Mostre que $G$ \'e amb\'{\i}gua.
        \item Fa\c{c}a uma gram\'atica n\~ao amb\'{\i}gua equivalente a $G$.
       \end{list}

 \item Apresente diagramas de estados para m\'aquinas de Turing que reconhe\c{c}am a linguagem
       $\{{\tt 0},{\tt 1}\}^*-\{{\tt 00}\}\{{\tt 0},{\tt 1}\}^*$:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Por estado final.
        \item Por parada.
       \end{list}

 \item Mostre que o problema da parada para linguagens de alto n\'{\i}vel (linguagens com
       procedimentos e comando \textit{enquanto}) \'e indecid\'{\i}vel.

\end{enumerate}

\end{document}