\documentclass[11pt, a4paper]{report}

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

\begin{document}

\vspace*{10mm}
\noindent {\it Fundamentos da Teoria da Computação}
\hfill $\mbox{1}^{\mbox{\underline{o}}}$ semestre de 2011 \\
\noindent Professor: Newton José Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\bf Primeira Prova}/Turma N \hfill {7/4/2011}

\vspace*{1mm}
\noindent \textbf{Duração:} 1 hora e 35 minutos. \\
\noindent \textbf{Valores:} 1,5 ponto por item.

\vspace*{2mm}
\noindent\textbf{Leia cada questão com cuidado. A interpretação faz parte da avaliação.}

\begin{enumerate}

 \item Seja $\Sigma=\{{\tt 0},{\tt 1},{\tt 2}\}$ e sejam as seguintes linguagens de alfabeto $\Sigma$:
       $L_1=\{{\tt 0},{\tt 1}\}\{{\tt 0},{\tt 1}\}^*$ e $L_2=\{{\tt 1}\}\{{\tt 1},{\tt 2}\}^*$.
       Para cada linguagem a seguir, escreva uma condição necessária e suficiente para
       que uma palavra pertença a ela, supondo que o alfabeto é $\Sigma$:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $L_2L_2$.
        \item $L_1\cap L_2$.
%        \item $L_1-L_2$.
       \end{list}
       Exemplo: uma condição necessária e suficiente para que uma palavra pertença a $L_1L_1$ é \emph{
       contém no mínimo dois símbolos e não contém {\tt 2}.} 
 \item Descreva as linguagens a seguir, todas sobre o alfabeto $\{{\tt 0},{\tt 1}\}$, usando apenas conjuntos
       finitos, opera\c c\~oes sobre conjuntos, concatena\c c\~ao e fecho de Kleene. Procure obter uma
       descri\c c\~ao bem concisa.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt 0}{\tt 1}^i{\tt 0}\,|\, i \mbox{ é ímpar}\}$.
        \item O conjunto das palavras no alfabeto $\Sigma=\{{\tt a},{\tt b},{\tt c}\}$ da forma $xyz$, em que $x$
              não contém {\tt a}, $y$ não contém {\tt b} e $z$ contém apenas {\tt c}s (um ou mais).
       \end{list}

 \item Obtenha gram\'aticas para as seguintes linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt 0}{\tt 1}^i{\tt 0}\,|\, i \mbox{ é ímpar}\}$.
        \item $\{w\in\{{\tt a},{\tt b},{\tt c}\}^*\,|\,w=w^R\}$.
       \end{list}

 \item Construa AFDs que reconhe\c cam as linguagens a seguir.
       Apresente apenas os diagramas de estados (que podem ser simplificados).
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt 0}{\tt 1}^i{\tt 0}\,|\, i \mbox{ é ímpar}\}$.
        \item O conjunto das palavras de $\{{\tt 0},{\tt 1}\}^*$ que cont\^em pelo menos um {\tt 00},
              mas nenhum {\tt 11}.
        \item $\{{\tt a},{\tt b}\}^*\{{\tt b},{\tt c}\}^*$.
       \end{list}

 \item Seja $\Sigma=\{{\tt}0,{\tt 1}\}$ e:
       \begin{itemize}
        \item $X=(\Sigma\Sigma)^*$
        \item $Y=\Sigma^*\{{\tt 11}\}\Sigma^*$.
       \end{itemize}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Desenhe os diagramas de estados de AFDs que reconhe\c{c}am $X$ e $Y$. O que reconhece $X$ deve ter
              dois estados e o que reconhece $Y$ deve ter três estados.
        \item Obtenha o diagrama de estados para o produto dos dois AFDs e diga quais s\~ao os estados finais
              para reconhecer $X\cap Y$ e $X-Y$.
       \end{list}
\end{enumerate}

\end{document}
