\documentclass[11pt, a4paper]{report}

\usepackage[brazil]{babel}
\usepackage[latin1]{inputenc}
\usepackage{fullpage}
\pagestyle{empty}
\newcounter{conta}

\begin{document}

\noindent {\it Fundamentos da Teoria da Computa\c{c}\~ao}
\hfill $\mbox{1}^{\mbox{\underline{o}}}$ semestre de 2012 \\
\noindent Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\bf Primeira Prova/Turma N} \hfill {\bf 03/04/2012}

\vspace*{3mm}
\noindent Os ítens das questões valem 1,5 pontos cada um, exceto o item (c) da questão 4, que vale 2.

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

 \item Descreva as linguagens a seguir, todas sobre o alfabeto $\{{\tt 0},{\tt 1}\}$,
       usando apenas \textit{conjuntos finitos} e opera\c{c}\~oes de \textit{uni\~ao}, \textit{interse\c{c}\~ao},
       \textit{concatena\c c\~ao} e \textit{fecho de Kleene}. Procure obter uma
       descri\c c\~ao bem concisa.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item O conjunto das palavras que cont\^em {\tt 01} como subpalavra.
        \item O conjunto das palavras com número par de {\tt 0}s.
       \end{list}

 \item Identifique as linguagens que s\~ao geradas pelas gram\'aticas a seguir:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $G_0=(\{A,B\},\{{\tt 0},{\tt 1}\},R_0,A)$.
              \begin{enumerate}
               \item[$R_0$:]  $A\,\rightarrow\,{\tt 0} A \,|\, B $
               \item[\ ]      $B\,\rightarrow\, B {\tt 1} \,|\, {\tt 01}$
              \end{enumerate}
        \item $G_1=(\{P,X\},\{{\tt 0},{\tt 1}\},R_1,P)$.
              \begin{enumerate}
               \item[$R_1$:]  $P\,\rightarrow\,{\tt 01} P {\tt 10} \,|\, X $
               \item[\ ]      $X\,\rightarrow\,{\tt 1} P {\tt 1} \,|\, \lambda$
              \end{enumerate}
       \end{list}

 \item Obtenha gramáticas que gerem:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item O conjunto das palavras de $\{{\tt 0},{\tt 1}\}^*$ que cont\^em {\tt 01} como subpalavra.
        \item O conjunto das palavras de $\{{\tt 0},{\tt 1}\}^*$ em que todo {\tt 0} \'e seguido de {\tt 1}.
        \item $\{w\in\{{\tt 0},{\tt 1},{\tt \#}\}^*\,|\, \mbox{ em } w\mbox{, não existem dígitos consecutivos }\}$ (Ou
              seja, entre quaisquer dois dígitos de uma palavra há pelo menos um {\tt \#}.)

       \end{list}

 \item Sejam
       \begin{itemize}
        \item $L_1=\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, w \mbox{ contém }{\tt 00}\}$;
        \item $L_2=\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, w \mbox{ contém ambos, }{\tt 0} \mbox{ e } {\tt 1}\}$.
       \end{itemize}
       Construa autômatos finitos determinísticos que reconheçam:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $L_1$.
        \item $L_2$.
        \item $L_2-L_1$. Para isto, faça o produto dos autômatos que reconhecem $L_2$ e $\overline{L_1}$
              (já que $L_2-L_1=L_2\cap\overline{L_1}$).
       \end{list}
\end{enumerate}

\end{document}
