\documentclass[12pt, a4paper]{report}

\usepackage[portuguese]{babel}
\usepackage{fullpage}
\pagestyle{empty}

\newcounter{conta}
\newcounter{conta2}

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

\vspace*{3mm}
\noindent {\bf As quest\~oes 1, 2 e 3 valem 3 pontos cada uma; a quest\~ao
4 vale 4,5 pontos; e a quest\~ao 5 vale 1,5 pontos.}

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

 \item Seja $L=\{\lambda,{\tt a},{\tt b}\}$.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Que linguagem \'e $L^0$?
        \item Que linguagem \'e $L^2$?
        \item Que linguagem \'e $L^n$, para $n\geq 0$?
        \item Quantas palavras tem $L^n$, para $n\geq 0$?
       \end{list}

 \item Descreva mais formalmente (usando conjuntos finitos, concatena\c c\~ao,
       uni\~ao, interse\c c\~ao, fecho de Kleene, etc.) as seguintes linguagens
       sobre o alfabeto $\{{\tt 0},{\tt 1}\}$:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
%        \item O conjunto das palavras com um n\'umero \'{\i}mpar de s\'{\i}mbolos.
        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, w$ come\c ca e termina com o mesmo s\'{\i}mbolo$\}$.
        \item O conjunto $X$ definido recursivamente assim:
              \begin{list}{\arabic{conta2})}{\usecounter{conta2}}
               \item $\lambda\in X$;
               \item se $x\in X$, ent\~ao ${\tt 1}x\in X$ e $x{\tt 0}\in X$.
              \end{list}
        \item O conjunto das palavras com um n\'umero par de {\tt 0}'s e \'{\i}mpar de {\tt 1}'s.
              (Sugest\~ao: use o operador de interse\c c\~ao.)
       \end{list}

 \item Sobre gram\'aticas:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Que linguagem \'e gerada pela gram\'atica $G$ definida a seguir?

              $G=(\{P,Z\},\{{\tt 0},{\tt 1}\},R,P)$.
               \begin{enumerate}
                \item[$R$:] $P\,\rightarrow\,{\tt 0} P {\tt 1}\,|\, Z$
                \item[\ ]   $Z\,\rightarrow\,{\tt 0} Z \,|\, {\tt 0}$
               \end{enumerate}
        \item Obtenha uma gram\'atica que gere $\{wxw^R\,|\,w\in\{{\tt a},{\tt b}\}^*, x\in\{{\tt b}\}^*$
               e $|x|$ \'e \'{\i}mpar$\}$.
       \end{list}

 \item Construa aut\^omatos finitos determin\'{\i}sticos (AFD's) para:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt 0}\}^*\{{\tt 1}\}^+\{{\tt 01}\}^*$.
        \item $\{{\tt a}^k{\tt b}^n\,|\, k+n\not= 2\}$.
        \item O conjunto das palavras sobre $\{{\tt 0},{\tt 1}\}$ com n\'umero \'{\i}mpar
              de {\tt 0}'s e sem {\tt 0}'s consecutivos.
       \end{list}

 \item Sejam dois AFD's $M_1=(E_1,\Sigma,\delta_1,i_1,F_1)$ e$M_2=(E_2,\Sigma,\delta_2,i_2,F_2)$.
       Fazendo-se o ``produto'' de $M_1$ e $M_2$ para obter o AFD
       $M_3=(E_1\times E_2,\Sigma,\delta_3,[i_1,i_2],F_3)$ tal que $L(M_3)=L(M_1)\cup L(M_2)$,
       como seriam obtidos:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\delta_3$?
        \item $F_3$?
       \end{list}

\end{enumerate}

\end{document}

