\documentclass[12pt, a4paper]{report}

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

\newcounter{conta}

\begin{document}
\pagestyle{empty}

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

\vspace*{3mm}
\noindent Pontua\c c\~ao: 2, 2, 2, 4, 4 e 1.
\begin{enumerate}
 \item Sejam $\Sigma=\{{\tt 0},{\tt 1}\}$,  $A=\Sigma^2$ e $B=\Sigma^*\{{\tt 0}\}$.
       Para cada uma das linguagens abaixo, d\^e uma propriedade necess\'aria
       e suficiente para que uma palavra perten\c ca \`a mesma:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $A^*$.
        \item $A-B$.
        \item $AB$.
        \item $A^*\cap B^+$.
       \end{list}

 \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 O conjunto das palavras que cont\^em {\tt 00} ou {\tt 11}, ou ambas,
              como subpalavras.
        \item O conjunto das palavras que n\~ao cont\^em a subpalavra {\tt 00}.
        \item O conjunto das palavras nas quais o n\'umero de {\tt 1}'s \'e par.
        \item O conjunto das palavras com n\'umero \'{\i}mpar de s\'{\i}mbolos
              que cont\^em a subpalavra ${\tt 0}{\tt 1}{\tt 0}$.
       \end{list}

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

        \item $G_2=(\{P,A,B\},\{{\tt 0},{\tt 1}\},R_2,P)$.
              \begin{enumerate}
               \item[$R_2$:] $P\,\rightarrow\,  A B$
               \item[\ ]     $A\,\rightarrow\,{\tt 0}B \,|\, {\tt 0}$
               \item[\ ]     $B\,\rightarrow\,{\tt 1}A \,|\, {\tt 1}$
              \end{enumerate}
       \end{list}

 \item Obtenha gram\'aticas para as seguintes linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{({\tt ab})^n x ({\tt ba})^n \,|\, x\in\{{\tt c}\}^*,
              |x|\geq 2 \mbox{ e } n\geq 0\}$.
        \item $\{{\tt a}^m{\tt b}^n\,|\, m\not=n\}$.
       \end{list}

 \item Construa aut\^omatos finitos determin\'{\i}sticos (AFD's) que reconhe\c cam
       as linguagens a seguir. Apresente apenas os diagramas de estados.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt 01}\}^*\{{\tt 1}\}^*\{{ \tt 10}\}^*$.
        \item O conjunto das palavras sobre $\{{\tt 0},{\tt 1}\}$ de tamanho par
              com dois {\tt 1}s.
       \end{list}

 \item Dados dois AFDs $M_1=(E_1,\Sigma,\delta_1,i_1,F_1)$ e $M_2=(E_2,\Sigma,\delta_2,i_2,F_2)$,
       especifique $E_3$, $\delta_3$, $i_3$ e $F_3$ de um AFD $M_3$ (produto de $M_1$ e
       $M_2$) que reconhe\c ca $L(M_3)=L(M_1)\cap L(M_2)$.
\end{enumerate}

\end{document}
