\documentclass[11pt, a4paper]{report}

\usepackage[brazil]{babel}
\usepackage[latin1] {inputenc}

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

\begin{document}

\noindent {\it Fundamentos da Teoria da Computa\c{c}\~ao}
\hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2010 \\
\noindent Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\bf Primeira Prova} \hfill {31/8/2010}

\vspace*{1mm}
\noindent \textbf{Dura\c{c}\~ao:} 1 hora e 30 minutos. \\
\noindent \textbf{Valor de cada quest\~ao:} 4 pontos (1 ponto extra!).

\vspace*{2mm}
\begin{enumerate}

 \item Sejam $\Sigma=\{{\tt}0,{\tt 1}\}$, $X=\Sigma^*\{{\tt 0}\}\Sigma^*$ e $Y=\Sigma^*\{{\tt 1}\}$.
       Descreva, de forma concisa, uma condi\c{c}\~ao necess\'aria e suficiente para que uma
       palavra perten\c{c}a a (não precisa dizer que a palavra é de {\tt 0}s e {\tt 1}s):
      \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $XY$.
        \item $X\cap Y$.
        \item $Y-X$.
        \item $Y^+$.
       \end{list}

 \item Seja $Z=\{{\tt 0}\}^*\{{\tt 1}\}^*$ e $W=\{{\tt 0}^n{\tt 1}^n\,|\,n\geq 1\}$.
       Obtenha gram\'aticas para as seguintes linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $Z$.
        \item $W$.
        \item $ZW$.
        \item $\{wxw^R\,|\, w\in\{{\tt 0},{\tt 1}\}^* \mbox{ e } x\in Z\}$.
       \end{list}

 \item Sejam $\Sigma=\{{\tt}0,{\tt 1}\}$, $X=\Sigma^*\{{\tt 0}\}\Sigma^*$ e $Y=\Sigma^*\{{\tt 1}\}$.
      \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Desenhe os diagramas de estados de dois AFDs $M_X$ e $M_Y$ tais que $L(M_X)=X$ e $L(M_Y)=Y$.
        \item Obtenha o diagrama de estados para o produto de $M_X$ e $M_Y$.
        \item Diga quais s\~ao os estados finais para o AFD que reconhece $X\cap Y$.
        \item Diga quais s\~ao os estados finais para o AFD que reconhece $Y-X$.
       \end{list}

 \item Seja $L=\{w\in\{{\tt a},{\tt b}\}^*\,|\, \mbox{ se $|w|>0$, o primeiro e o \'ultimo
       s\'{\i}mbolos de $w$ s\~ao id\^enticos}\}$.
      \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Apresente o diagrama de estados de um AFD que reconhe\c{c}a $L$.
        \item Expresse $L$ usando apenas subconjuntos finitos de $\{{\tt a},{\tt b}\}^*$ e opera\c{c}\~oes
              dentre: uni\~ao, interse\c{c}\~ao, concatena\c{c}\~ao e fecho de Kleene.
       \end{list}

\end{enumerate}

\end{document}

