\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/Solu\c c\~ao do professor}

\begin{enumerate}
 \item
% {\footnotesize 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}}

%       {\em Solu\c c\~ao:}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Tem um n\'umero par de s\'{\i}mbolos.
        \item \'E {\tt 01} ou {\tt 11}.
        \item Tem pelo menos tr\^es s\'{\i}mbolos e o \'ultimo \'e {\tt 0}.
        \item Tem um n\'umero par de s\'{\i}mbolos e o \'ultimo \'e {\tt 0}.
       \end{list}


 \item
% {\footnotesize 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}}

%       {\em Solu\c c\~ao:}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt 0},{\tt 1}\}^*\{{\tt 00},{\tt 11}\}\{{\tt 0},{\tt 1}\}^*$.
        \item $\{{\tt 0},{\tt 01}\}^*\{\lambda,{\tt 0}\}$.
        \item $(\{{\tt 0}\}^*\{{\tt 1}\}\{{\tt 0}\}^*\{{\tt 1}\})^*\{{\tt 0}\}^*$.
        \item $\{{\tt 0},{\tt 1}\}(\{{\tt 0},{\tt 1}\}\{{\tt 0},{\tt 1}\})^*\cap
               \{{\tt 0},{\tt 1}\}^*\{{\tt 010}\}\{{\tt 0},{\tt 1}\}^*$
       \end{list}

 \item
% {\footnotesize 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}}

%       {\em Solu\c c\~ao:}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $(\{{\tt 0},{\tt 1}\}^3)^*$.

        \item $L_AL_B$, onde $L_A=\{{\tt 0}\}\{{\tt 10}\}^*\{\lambda,{\tt 1}\}$
              e $L_B=\{{\tt 1}\}\{{\tt 01}\}^*\{\lambda,{\tt 0}\}$.
       \end{list}


 \item
% {\footnotesize 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}}

%       {\em Solu\c c\~ao:}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item \begin{enumerate}
               \item[\ ] $P\,\rightarrow\, {\tt ab} P {\tt ba} \,|\, X$ 
               \item[\ ] $X\,\rightarrow\,{\tt c} X \,|\,{\tt cc}$
              \end{enumerate}
        \item \begin{enumerate}
               \item[\ ] $P\,\rightarrow\, {\tt a} P {\tt b} \,|\, A \,|\, B$ 
               \item[\ ] $A\,\rightarrow\,{\tt a} A \,|\,{\tt a}$
               \item[\ ] $B\,\rightarrow\,{\tt b} B \,|\,{\tt b}$
              \end{enumerate}
       \end{list}

 \item
% {\footnotesize 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}}

%       {\em Solu\c c\~ao:}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $(\{1,2,3,4,5,e\},\{{\tt 0},{\tt 1}\},\delta,1,\{1,3,4\})$, onde
              $\delta$ \'e dada por:
              \begin{center}
               \begin{tabular}{c|cc}
                $\delta$ & {\tt 0} & {\tt 1} \\ \hline
                       1 &   2 &   3 \\
                       2 & $e$ &   1 \\
                       3 &   4 &   3 \\
                       4 & $e$ &   5 \\
                       5 &   4 & $e$ \\
                     $e$ & $e$ & $e$
               \end{tabular}
              \end{center}
        \item $(\{p0,i0,p1,i1,p2,i2,e\},\{{\tt 0},{\tt 1}\},\delta,p0,\{p2\})$, onde
              $\delta$ \'e dada por:
              \begin{center}
               \begin{tabular}{c|cc}
                $\delta$ & {\tt 0} & {\tt 1} \\ \hline
                    $p0$ & $i0$ & $i1$ \\
                    $i0$ & $p0$ & $p1$ \\
                    $p1$ & $i1$ & $i2$ \\
                    $i1$ & $p1$ & $p2$ \\
                    $p2$ & $i2$ & $e$ \\
                    $i2$ & $p2$ & $e$ \\
                     $e$ & $e$ & $e$
               \end{tabular}
              \end{center}

       \end{list}

 \item
% {\footnotesize 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)$.}

%       {\em Solu\c c\~ao:}
       \begin{itemize}
        \item $E_3=E_1\times E_2$;
        \item $\delta_3([e_1,e_2],a)=[\delta_1(e_1,a),\delta_2(e_2,a)]$ para cada
              $[e_1,e_2]\in E_3$ e $a\in\Sigma$;
        \item $i_3=[i_1,i_2]$; e
        \item $F_3=F_1\times F_2$.
       \end{itemize}
\end{enumerate}

\end{document}
