\documentclass[11pt, a4paper]{report}

\usepackage[portuguese]{babel}
\usepackage{fullpage}
\pagestyle{empty}
\newcounter{conta}
\usepackage{gastex}
\usepackage[usenames]{color}

\begin{document}

\vspace*{10mm}
\noindent {\it Fundamentos da Teoria da Computa\c{c}\~ao}
\hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2009 \\
\noindent Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\bf Primeira Prova}/Turmas B e E/Solu\c{c}\~ao do professor \hfill {10/9/2009}

\vspace*{1mm}
%\noindent \textbf{Dura\c{c}\~ao:} 1 hora e 30 minutos. \\
%\noindent \textbf{Valor de cada quest\~ao:} 3 pontos (1 ponto por item).

%\vspace*{2mm}
\begin{enumerate}
 \item {\footnotesize Sejam $\Sigma=\{{\tt 0},{\tt 1}\}$, $X=\Sigma^+\{{\tt 1}\}$ e $Y=\Sigma^*\{{\tt 0}\}\Sigma$.
       Descreva de forma clara e precisa, em portugu\^es, as linguagens a seguir. N\~ao \'e necess\'ario
       dizer que as palavras s\~ao de {\tt 0}s e {\tt 1}s. Por exemplo:
       \begin{quote}
        $X$: conjunto das palavras que terminam com {\tt 01} ou {\tt 11}.
       \end{quote}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $Y$.
        \item $X\cap Y$.
        \item $X-Y$.
       \end{list}}
       
       \textit{Solu\c{c}\~ao}:
       
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $Y$: conjunto das palavras que terminam com {\tt 00} ou {\tt 01}.
        \item $X\cap Y$: conjunto das palavras que terminam com {\tt 01}.
        \item $X-Y$: conjunto das palavras que terminam com {\tt 11}.
       \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 come\c{c}am com {\tt 0} e cont\^em pelo menos um {\tt 1}.
        \item O conjunto das palavras que cont\^em {\tt 00}.
        \item O conjunto das palavras que n\~ao cont\^em {\tt 00}.
       \end{list}}
       
       \textit{Solu\c{c}\~ao}:
       
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt 0}\}^+\{{\tt 1}\}\{{\tt 0},{\tt 1}\}^*$.
        \item $\{{\tt 0},{\tt 1}\}^*\{{\tt 00}\}\{{\tt 0},{\tt 1}\}^*$.
        \item $\{{\tt 1},{\tt 01}\}^*\{\lambda,{\tt 0}\}$.
       \end{list}

 \item {\footnotesize Sejam $A=\{{\tt 0}\}^*\{{\tt 0},{\tt 1}\}\{{\tt 1}\}^*$ e $B=\{{\tt 0}^n{\tt 1}^n\,|\,n\geq 0\}$.
       Obtenha gram\'aticas para as seguintes linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $A$.
        \item $B$.
        \item $B^*$.
       \end{list}}
       
       \textit{Solu\c{c}\~ao}:
       
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $(\{P\},\{{\tt 0},{\tt 1}\},R,P)$, em que $R$ \'e constitu\'{\i}do de:
              \begin{quote}
               $P \,\rightarrow\, {\tt 0}P \,|\, P{\tt 1} \,|\, {\tt 0} \,|\, {\tt 1}$
              \end{quote}
        \item $(\{P\},\{{\tt 0},{\tt 1}\},R,P)$, em que $R$ \'e constitu\'{\i}do de:
              \begin{quote}
               $P \,\rightarrow\, {\tt 0}P{\tt 1} \,|\, \lambda$
              \end{quote}
        \item $(\{P,X\},\{{\tt 0},{\tt 1}\},R,P)$, em que $R$ \'e constitu\'{\i}do de:
              \begin{quote}
               $P \,\rightarrow\, XP \,|\, \lambda$ \\
               $X \,\rightarrow\, {\tt 0}X{\tt 1} \,|\, {\tt 01}$
              \end{quote}
       \end{list}
 
 \item {\footnotesize 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 01},{\tt 10}\}\{{\tt 0},{\tt 1}\}^*$.
        \item $\{{\tt 0}\}^*\{{\tt 0},{\tt 1}\}\{{\tt 1}\}^*$.
        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, w$ n\~ao cont\'em tr\^es s\'{\i}mbolos consecutivos id\^enticos$\}$.
       \end{list}}
       
       \textit{Solu\c{c}\~ao}:
       
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item \

              \mbox{\setlength{\unitlength}{1mm}
              \begin{picture}(120,20)\setlength{\unitlength}{1mm}
               \gasset{Nw=5, Nh=5, Nmr=2.5, loopdiam=6}

               \node[Nmarks=i](i)(20,12){}
               \node(1)(35,19){}
               \node(2)(35,5){}
               \node[Nmarks=r](3)(50,12){}

               \drawedge[curvedepth=0](i,1){{\tt 0}}
               \drawedge[curvedepth=0, ELside=r](i,2){{\tt 1}}
               \drawedge[curvedepth=0](1,3){{\tt 1}}
               \drawedge[curvedepth=0,ELside=r](2,3){{\tt 0}}
               \drawloop[loopangle=0](3){{\tt 0},{\tt 1}}
              \end{picture}
             } \\
        \item \

              \mbox{\setlength{\unitlength}{1mm}
              \begin{picture}(120,15)\setlength{\unitlength}{1mm}
               \gasset{Nw=5, Nh=5, Nmr=2.5, loopdiam=6}

               \node[Nmarks=i](i)(20,10){}
               \node[Nmarks=r](1)(35,10){}
               \node[Nmarks=r](2)(50,10){}

               \drawedge[curvedepth=0](i,1){{\tt 0}}
               \drawedge[curvedepth=0](1,2){{\tt 1}}
               \drawedge[curvedepth=-6,ELside=r](i,2){{\tt 1}}
               
               \drawloop[loopangle=90](1){{\tt 0}}
               \drawloop[loopangle=90](2){{\tt 1}}
              \end{picture}
             } \\
        \item \

              \mbox{\setlength{\unitlength}{1mm}
              \begin{picture}(120,20)\setlength{\unitlength}{1mm}
               \gasset{Nw=5, Nh=5, Nmr=2.5, loopdiam=6}

               \node[Nmarks=ir](i)(20,13){}
               \node[Nmarks=r](1)(35,21){}
               \node[Nmarks=r](2)(55,21){}
               \node[Nmarks=r](3)(35,5){}
               \node[Nmarks=r](4)(55,5){}

               \drawedge[curvedepth=0](i,1){{\tt 0}}
               \drawedge[curvedepth=0, ELside=r](i,3){{\tt 1}}
               \drawedge[curvedepth=0](1,2){{\tt 0}}
               \drawedge[curvedepth=3](1,3){{\tt 1}}
               \drawedge[curvedepth=0,ELpos=30,ELside=r](2,3){{\tt 1}}
               \drawedge[curvedepth=3](3,1){{\tt 0}}
               \drawedge[curvedepth=0](3,4){{\tt 1}}
               \drawedge[curvedepth=0, ELside=r, ELpos=30](4,1){{\tt 0}}
              \end{picture}
             } \\
       \end{list}

 \item {\footnotesize Seja $\Sigma=\{{\tt}0,{\tt 1}\}$ e:
       \begin{itemize}
        \item $A=\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, \mbox{ o n\'umero de {\tt 0}s em $w$ \'e par}\}$;
        \item $B=\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 $A$ e $B$.
        \item Obtenha o diagrama de estados para o produto dos dois AFDs.
        \item Diga quais s\~ao os estados finais para o AFD que reconhece $A\cup B$ e para
              o AFD que reconhece $A\cap B$.
       \end{list}}
       
       \textit{Solu\c{c}\~ao}:
       
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item \

              \mbox{\setlength{\unitlength}{1mm} \footnotesize
              \begin{picture}(120,10)\setlength{\unitlength}{1mm}
               \gasset{Nw=5, Nh=5, Nmr=2.5, loopdiam=6}

               \put(5,5){\makebox(0,0)[c]{$M_A$:}}
               \node[Nmarks=ir](1)(20,5){1}
               \node(2)(40,5){2}

               \drawedge[curvedepth=3](1,2){{\tt 0}}
               \drawedge[curvedepth=3](2,1){{\tt 0}}
 
               \drawloop[loopangle=90](1){{\tt 1}}
               \drawloop[loopangle=90](2){{\tt 1}}

               \put(55,5){\makebox(0,0)[c]{$M_B$:}}
               \node[Nmarks=i](a)(70,5){a}
               \node(b)(90,5){b}
               \node[Nmarks=r](c)(110,5){c}

               \drawedge[curvedepth=3](a,b){{\tt 1}}
               \drawedge[curvedepth=3](b,a){{\tt 0}}
               \drawedge[curvedepth=0](b,c){{\tt 1}}
 
               \drawloop[loopangle=90](a){{\tt 0}}
               \drawloop[loopangle=90](c){{\tt 0},{\tt 1}}
              \end{picture}
             } \\
        \item \

              \mbox{\setlength{\unitlength}{1mm} \footnotesize
              \begin{picture}(120,20)\setlength{\unitlength}{1mm}
               \gasset{Nw=5, Nh=5, Nmr=2.5, loopdiam=6}

               \node[Nmarks=i](1a)(20,20){1a}
               \node(2a)(20,5){2a}
               \node(1b)(40,20){1b}
               \node(2b)(40,5){2b}
               \node(1c)(60,20){1c}
               \node(2c)(60,5){2c}

               \drawedge[curvedepth=3](1a,2a){{\tt 0}}
               \drawedge[curvedepth=0](1a,1b){{\tt 1}}
               \drawedge[curvedepth=3](2a,1a){{\tt 0}}
               \drawedge[curvedepth=0,ELside=r](2a,2b){{\tt 1}}
               \drawedge[curvedepth=0,ELside=r,ELpos=35](1b,2a){{\tt 0}}
               \drawedge[curvedepth=0](1b,1c){{\tt 1}}
               \drawedge[curvedepth=0,ELpos=35](2b,1a){{\tt 0}}
               \drawedge[curvedepth=0,ELside=r](2b,2c){{\tt 1}}
               \drawedge[curvedepth=3](1c,2c){{\tt 0}}
               \drawedge[curvedepth=3](2c,1c){{\tt 0}}
 
               \drawloop[loopangle=0](1c){{\tt 1}}
               \drawloop[loopangle=0](2c){{\tt 1}}
              \end{picture}
             } \\
        \item $F_\cup=\{\mbox{1a},\mbox{1b},\mbox{1c},\mbox{2c}\}$, $F_\cap=\{\mbox{1c}\}$.
       \end{list}
\end{enumerate}

\end{document}
