\documentclass[11pt, a4paper]{report}

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

\begin{document}

\vspace*{1cm}
\noindent {\it Fundamentos da Teoria da Computa\c{c}\~ao}
\hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2009 \\
\noindent Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\bf Quarta Prova}           \hfill {26/11/2009}

\vspace*{1mm}
\noindent \textbf{Dura\c{c}\~ao:} 1 hora e 30 minutos. \\
\noindent \textbf{Valor de cada quest\~ao:} a primeira vale 3 e as outras 4 pontos cada uma.

\vspace*{5mm}
\begin{enumerate}
 \item Seja o alfabeto $\Sigma=\{{\tt a},{\tt e},{\tt i},{\tt o},{\tt u}\}$.
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
        \item Construa uma MT padr\~ao com \textit{um \'unico estado\/} que reconhe\c ca $\Sigma^+$;
        \item Construa uma MT padr\~ao com \textit{uma \'unica transi\c{c}\~ao\/} que reconhe\c ca $\Sigma^+$.
        \item Construa uma MT padr\~ao com \textit{o menor n\'umero poss\'{\i}vel de estados e transi\c{c}\~oes\/}
              que reconhe\c ca $\Sigma^*$.
       \end{list}

 \item Construa o diagrama de estados de uma MT que reconhe\c ca a linguagem:
       \[\{xx^Ry\,|\,x\in\{{\tt a},{\tt b}\}^+ \mbox{ e } y\in\{{\tt a},{\tt c}\}^*\}\mbox{.}\]
       \emph{Dica}: Utilize duas fitas e n\~ao determinismo.

 \item Construa uma gram\'atica irrestrita que gere $\{{\tt a}^n{\tt b}^n{\tt a}^n\,|\,n\geq 1\}$.
       Caso a gram\'atica tenha menos de 5 regras voc\^e ganha mais um ponto.

 \item Responda sim ou n\~ao. Para cada resposta certa voc\^e ganha meio ponto
       e para cada resposta errada perde meio ponto:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
        \item Um aut\^omato finito n\~ao determin\'{\i}stico pode reconhecer uma linguagem n\~ao recursiva.
        \item Uma m\'aquina de Turing n\~ao determin\'{\i}stica com duas fitas tem um poder computacional
              maior que o de uma determin\'{\i}stica de uma fita s\'o.
        \item Qualquer linguagem livre do contexto \'e recursiva.
        \item Se $L$ n\~ao \'e recursiva, $\overline{L}$ tamb\'em n\~ao \'e.
        \item Se $L$ n\~ao \'e recursivamente enumer\'avel, $\overline{L}$ tamb\'em
              n\~ao \'e.
        \item Qualquer linguagem recursivamente enumer\'avel pode ser gerada por gram\'atica irrestrita.
        \item Se $L_1$ \'e recursivamente enumer\'avel e $L_2$ \'e recursiva, $L_1-L_2$ \'e recursivamente enumer\'avel.
        \item Se $L_1$ \'e recursiva e $L_2$ \'e recursivamente enumer\'avel, $L_1-L_2$ \'e recursivamente enumer\'avel.
       \end{list}

\end{enumerate}

\end{document}
 