\documentclass[12pt, a4paper]{report}

\addtolength{\topmargin}{-1cm}
\addtolength{\textheight}{1cm}
\newcounter{conta}
\pagestyle{empty}
\begin{document}
 
\noindent Bacharelado em Ci\^{e}ncia da Computa\c{c}\~{a}o
\hfill DCC/ICEx/UFMG
 
\noindent {\it Fundamentos da Teoria da Computa\c{c}\~ao}
\hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2001
 
\noindent Professor: Newton Jos\'{e} Vieira
 
\noindent {\bf Primeira Prova} \hfill 23/01/02
 
\vspace*{3mm}
\noindent {Cada item de cada quest\~ao vale 1,5 pontos.}

\begin{enumerate}
 \item Descreva, em portugu\^es coloquial, as seguintes linguagens sobre o alfabeto $\{0,1\}$:
       \begin{enumerate}
        \item[(a)] $\{0\}\{0,1\}^*\cup\{0,1\}^*\{1\}$
        \item[(b)] $\{0,1\}^*\{01\}\{11\}^*$
       \end{enumerate}
       [Exemplo: $\{0,1\}^*\{1\}\{0,1\}$ \'e {\em o conjunto das palavras cujo pen\'ultimo
                 s\'{\i}mbolo \'e 1\/}.]

 \item Obtenha gram\'aticas para as seguintes linguagens:
       \begin{enumerate}
        \item[(a)] $\{w\in\{a,b,c\}^*\,\,|\,\, w \mbox{ n\~ao cont\'em a subpalavra $cba$}\}$.
        \item[(b)] $\{ww^R\,\,|\,\, w\in\{a,b\}^* \mbox{ e $w$ cont\'em pelo menos um $a$
                   e um $b$}\}$.
       \end{enumerate}

 \item Construa aut\^omatos finitos determin\'{\i}sticos (AFD's) para reconhecer as seguintes
       linguagens de alfabeto $\{0,1\}$:
       \begin{enumerate}
        \item[(a)] O conjunto das palavras cujo pen\'ultimo s\'{\i}mbolo \'e 1.
        \item[(b)] $\{w010\,\,|\,\, w\in\{0,1\}^*\}$.
        \item[(c)] $(\{1\}\cup\{0\}\{1\}^*\{0\})^*$.
       \end{enumerate}

 \item Sejam os AFD's a seguir:
       \begin{enumerate}
        \item[$M_1$:] $(\{p,i_0,i_1\},\{0,1\},\delta_1,p,\{i_1\})$, onde $\delta_1$ \'e dada por:\

                      \begin{tabular}{c|cc}
                       $\delta$ & 0 & 1 \\ \hline
                           $p$  & $i_0$ & $i_1$ \\
                         $i_0$  & $p$ & $p$ \\
                         $i_1$  & $p$ & $p$
                      \end{tabular}
        \item[$M_2$:] $(\{n,s\},\{0,1\},\delta_2,n,\{s\})$, onde $\delta_2$ \'e dada por:

                      \begin{tabular}{c|cc}
                       $\delta$ & 0 & 1 \\ \hline
                           $n$  & $s$ & $n$ \\
                           $s$  & $s$ & $s$
                      \end{tabular}
       \end{enumerate}

       \begin{enumerate}
        \item[(a)] Que linguagens s\~ao reconhecidas por $M_1$ e $M_2$?
        \item[(b)] Usando produto de aut\^omatos, construa AFD's para $L(M_1)\cup L(M_2)$ e
                   $L(M_1)\cap L(M_2)$.
        \item[(c)] Minimize os AFD's obtidos em (b).
       \end{enumerate}

%\begin{flushright}
% {\bf Continua no verso.}
%\end{flushright}

%\pagebreak
\end{enumerate}

\end{document}
 
